Microsoft began offering Linux virtual machine hosting on its Azure platform this week.
I created an Ubuntu 12.04 server this morning and everything worked smoothly. I found it much easier to create and connect to a virtual machine on Azure than on Amazon EC2.