My wife and I travelled through Europe around the same time as you (most of 2007 and some of 2008). We managed to spend about $25000 for both of us for a year's travel. There's really a ton of ways to travel cheaply if you do your research.

One resource that was invaluable for us was HelpExchange (http://www.helpx.net). Basically the idea is that you exchange helping out someone (usually for about 4 hours a day) in exchange for room and board. On it's own, it's not the greatest deal in the universe, but you can find some really interesting places. During our stay, we did help exchange at:

- A farm in Sweden, where we helped out at the market, got to see some amazing countryside with super friendly people.

- A pub / hostel in a small village in Yorkshire, where our "job" was really just to chat with the locals and pull the occasional pint.

- An absolutely beautiful chateau in Normandy, with 4 other helpx people, including a chef who made the most amazing food ever.

- A camel farm in Austria, where we actually learned to be pretty good horseback riders in 4 weeks (due to dressage lessons every day after we took the camels for a walk)