I'd go with one of the solid state offerings from $300-$500. The Gilmore Lite/Dynalo, M^3, CK2III, and EC/SS will all do a terrific job. Tubes cost more; don't bother with the cheap tube amps. The cost factor with tubes stems from the necessity of using quality transformers - you don't want a cheap one. The laminations and windings are important. Those take quality copper and iron - commodity prices for those are similar the world over and those costs are higher than labor. Don't think a transformer from somewhere with cheap labor is cheap because of that, it's cheap because they skimped on the raw ingredients. You're better off buying from a name brand.
The difference is that tubes need high voltage to run. 300V is common, so are higher voltages. To get line voltage up there, you need some serious transformers. And you have to pay for the raw materials to do that. Aside from that, tubes run hotter (generally speaking) than solid state, so a bit more work has to be done with the casing. Every hole drilled adds cost.
So a quality tube amp will cost more. Solid state will run off 12V-16V or so and the chips tend to have lots of filtering and regulation (I'm not as up on solid state design, so someone correct me if I'm wrong) on board, so you can get away with inexpensive wallwart transformers. Tube amps need a big power transformer, often a separate filament transformer, and the good designs use chokes to filter the power some more. The cost of those really adds up - you can easily spend $200 on the transformers alone for tubes, while a good wallwart for solid state can be had for $40.
Anyhow, solid state is your friend if you want high quality at a low price. There are a lot of confirmed tubeheads here (I am) and chips don't glow in the dark. They can, however, sound really good. You're better off with a $300 solid state amp than a $300 tube amp.
If you really want to save money, gather parts for a DIY amp yourself. That's easy and you can spread out the purchases over time. You can also scrounge and repurpose a case from something else. You can learn more in the DIY Forum. Cases are expensive, but you can hunt one down yourself for $5 or $10. When you get everything together, negotiate with a builder and send everything off. If the builder doesn't have to source everything, it'll save him lots of time and you lots of money.
Another option is to look for a used amp. You'll see them in the For Sale Forum. That's a good way to go because 99% of the time the seller is upgrading or selling something that's been unused. Unlike cars, people don't usually sell their problems here.
And after all that, I'd say give your receiver a shot. Some work great and you might have one that does. At the least, get the HD-600 (I love mine) and use the receiver while you do your homework and learn more about amps. You don't have to buy immediately, no matter how tempting it seems. Hold off and read up before you buy.