You can find many other UML providers listed at
http://www.usermodelinux.org/ (click on the "Commercial" category at the right).
I've heard good things about johncompanies.com. I have a friend who has an account there and loves it. They supposedly have the ability to transparently move a server throughout the cluster. Also take careful note of the special pricing for open-source developers.
When I was looking for a UML-based hosting service, I ended up choosing linode over johncompanies because of the price and because of how well-presented linode is. Linode has a community, support forums, irc, and a nice webpage for managing your host. Other companies may have something similar, but I couldn't tell from their webpages.
Lastly, if you do browse the usermodelinux.org list of providers, you will find some providers that charge less than linode. Since you are looking only for a backup server, this serve you well. But for a server that gets any real use, be very wary -- in general, you get what you pay for.