Not very experienced in eastern Europe. I hope others will offer more info.

One enjoyable place I’ve visited:
Bay of Kotor, Montenegro (Budva was very pleasant)
Dubrovnik is well worth it, too. Trying to save money was not as easy as we thought it would be.

Some of the “standard” visits in Eastern Europe aren’t all that much cheaper than Western Europe. Prague, Krakow and Budapest aren’t necessarily cheap.

I like Cil’s suggestion of “former Yugoslavia.” I loved Slovenia and Croatia, but neither was particularly cheap. Other countries/areas in the region should be somewhat cheaper and you can find a big variety of terrain, activities, ethnic differences, cities in a relatively small area which might cut down on your city to city travel expense.

To go really cheap, Bulgaria is a fascinating and under touristed country. Gert out of Sofia, and check some of the charming and naturally beautiful cities like Plovdiv and Veliko Tarnova.

Budapest is also a fantastic city with an eastern flavor but closer to Central Europe. If you go to Budapest, I always recommend Backpacker’s Guesthouse; a very friendly commune feeling hostel.

Never been there but I heard there are a lot of good things to do and spend vacation

Loads of options in the east, and almost all of them are definitely cheaper than western Europe, even Krakow, which really is a great destination by the way.
Looking at your name I assume you’re from Belgium or the Netherlands? Ryanair and Wizz will be opening some new routes from Eindhoven starting in april 2011: Tallinn, Vilnius and Belgrade. I’ve been to the last two and I think both places are well worth a visit. Vilnius is cheaper than Belgrade, but for both places goes that when you leave them prices drop dramatically. Try Kaunas in Lithuania (1 hour, Lt 19,), or even go to Minsk in Belarus (make sure you have a visa, 4 hours, Lt 38,). And visit Novi Sad and Fruska Gora in Serbia (1,5 hour, RSD 610,- by bus, RSD 288,- by train).
Another cool option is Lviv, Ukraine, easily reached with Wizzair from Dortmund.

I’ve been to Estonia and loved it! I’m think it would be failrly reasonably priced to travel through Poland into Lituania, Latvia and even Estonia. Use the buses as rail travel is slow.The major cities will be more expensive but the smaller centres will still be quite cheap. Either way it will be cheaper than western Europe. Most people won’t speak english but will try their best to help you. It would be quite awsome. No matter where you end up going let us know how it goes!