I use a share at www.gandi.net, 1 share isn't too expensive. In my experience they respond the same day to support emails, and you can enable temporary console access via their website in case you really messed up your installation.

update: gandi is in france.