I'm glad to here they're taking care of you. It's always nice to see a company that does what it should
One more thing that must have just slipped my mind yesterday. The A5s say they're only down 1.5dB at 50Hz. The Klipsch are rated down to 30Hz, but they don't give any qualifiers on how many dB down they are at that point... at least on the sources I've seen.
If the bass that you're missing is in the 30-40 Hz range, it's possible that the Promedias were indeed much better at producing those frequencies. I think your under bookshelf resonant type scenario is probably a more significant influence though.
As for the amp getting hot, that would be something to ask their customer support or check for posts on the issue from random forum posts from users. Depending on the kind of amp design they used, this could be perfectly normal or a sign of a defect. Maybe wait to see if your replacement set works first?
As for a sub, you could indeed get one that's cheaper than the $350 one from Audioengine. Their s8 is probably pretty impressive for its size, but you should be able to get a lot more sub for the money if you so desire (and have room for it).
If you were to spend that $350 on a sub, you could get something like an entry level unit from Elemental Designs for example
http://www.edesignaudio.com/index.php?cPath=2_41
For something cheaper, there are some other alternatives.
For just about the absolute cheapest option, Dayton has some.
http://www.parts-express.com/pe/showdetl.cfm?Partnumber=300-633
http://www.parts-express.com/pe/showdetl.cfm?Partnumber=300-635
Between that ~$100 range and the $350 range, there are a lot of other options.
The BIC H-100 used to be a popular option. I think they replaced that with a new model though and I haven't been keeping up on whether that one is also a good bang for the buck option.
There are usually a few clearance / limited time type deals out there too from regular retail brands that would be good options.