Windows Home Server backup doesn't work that way.

A full restore, using the Restore CD, would wipe your (freshly upgraded) OS and restore the Vista Premium you're looking to get away from.
Your best bet, if you don't want to reinstall your applications, is an upgrade-in-place. The Anytime upgrade would be ideal if you could get it to work, but you should be able to install Ultimate as an upgrade over Premium. If you can't do either of those (requiring a fresh installation) then you will have to reinstall your applications, but you'll be able to get your files back from any recent backup.
Have you called Microsoft about your problem with an Anytime upgrade?