Not about your itinerary but about this: "We are open to hostels but due to the longevity of the trip we are worried our bags might be slightly too large for hostel lockers, and were hoping for a little more privacy if possible"

1) pack light - no matter where you end up staying. A longer trip doesn't mean extra luggage.

2) Many Hostels have private rooms

You should't miss Eze and Saint Paul de Vence in Cote d'azur.
Monaco can also be included in your South France itinerary.

Sorry I forgot to mention Port Grimaud which is close to St.Tropez

Thank you! Yes Janisj I am going to try my best, just some lockers say backpacks fit and mine will be a but larger and on wheels

When I stayed in hostels in the UK (a few years ago) I found that almost all of them had laundry facilities, usually coin operated. I'm sure the hostels in France and Spain will, too. After all, most backpackers don't carry around large suitcases full of clothes.

I suggest 2 very central,clean and budget hotels which we stayed in Barcelona.
In both hotels breakfast was included in the room price.(75-80 €/night for a double room)

HOTEL AUTOHOGAR www.hotelautohogarbarcelona.com
CAFE ESPANOL on the ground floor serves delicious seafood and tapas and the waiters are extremely friendly.If you go there say Hi to David please

HOTEL PARALLEL www.hotelparalel.com is the second option.
have a nice holiday

This is in the midst of high season. If it were possible could you go earlier or later?

In Barcelona I use to stay in Hostal Orleans, basic hotel standard, private bathroom, aircondition, free safe, tv, 24h desk etc. In the vibrant and medieval Born district close to everything. 70€ for a double in August.
Hostal Orleans:
http://www.hostalorleans.com/index.php?lang=en
Reviews and more info:
http://www.booking.com/hotel/es/hostal-orleans.en.html

Brilliant tapas bars, cafés, restaurants and nightlife on your doorstep and ten minutes walk from the Barceloneta beach. Very safe, people all over long into the night and 20 meters away from almost 24/7 café/bar/restaurant Navia which is very popular with locals.

About El Born: http://www.barcelona-tourist-guide.com/en/areas/el-born.html
El Born on tripadvisor: http://www.tripadvisor.com/Attraction_Review-g187497-d254718-Reviews-El_Born-Barcelona_Catalonia.html

We are on a budget so would prefer to spend 100 euros or less per night in the hotel.>

If under 26 then you can get a Eurail Youthpass and ride the rails at will cheaply and use overnight trains where you save on the cost of a night in a hostel - today about $20-25 in main cities p.p.

Anyway there are lots of folks your age riding the rails in Europe so strongly consider that - for lots of great info on European trains and railpasses and alternatives like discounted online tickets (which however are generally train-specific and must be booked weeks in advance to get as they are sold in limited numbers and sell out often weeks in advance and cannot be refunded - so if you want to set your itinerary in stone and are not taking more than a handful of trips that could be the best route. For flexibility to chose which trains you'll take when there look at a Youthpass - fully flexible tickets cost a ton of money so in that case a pass may be your best bet.
For lots of great info on the European train system I always spotlight these IMO fantastic sites - www.ricksteves.com; www.budgeteuropetravel.com and www.seat61.com (good info the latter on online discounted ducats).

In the big cities you mention you should be able to find hotels in the Ibis chain at the price you mentioned. Part of the big Accor hotel group, the Ibis places are reliable because they are all pretty much alike (which in turn means no distinctive character.) http://ibishotel.ibis.com/gb/booking/hotels-list.shtml
And no, I am not a shill for Ibis. The easy of booking, and the reliability, compensates for the lack of charm. Anyhow, the chain's success has encouraged competition from other operators which you can find on the Internet. Act quickly as it looks like a big year for tourism in western Europe.

I am a huge fan of IBIS hotels like Southam talks about above - great deals and they also do have deals at times on say weekends when their normal business clientele is not there.

ETAP is from the same Accor chain and a bit cheaper than IBIS and not quite as luxurious (well IBIS ain't a luxury hotel but it is very very comfy, etc) as IBIS - sometimes they adjoin each other, like near Amsterdam Schiphol airport.

www.accorhotels.com

Act quickly as it looks like a big year for tourism in western Europe.>

Just curious as to why it looks like that - Europeans themselves are reeling and they make up most of the tourism in Europe - what do you base this statement on - just curious as it seems an oxymoron given Europeans dicey economic status.

Yup the month of August though in general is the most hectic travel month for the areas you are going - many northern Europeans have vacations then - most of France does and they flee south from their not unusually cool and at times wet summers.

Not the optimal time to travel in Spain, southern France or Italy - September would be great! Crowds clear out dramatically after the last weekend in August.

The Nice area is especially mobbed during August - terribly mobbed IME - be sure to book your hotel or hostel there very very early.

Some hostels now have private rooms.

You can take an overnight train between Paris and Nice - save travel time and the cost of a night in a hotel. www.voyages-sncf.com for schedules and fares and possible some really cheap fares if booked far in advance.