As far as I've looked I've found webfaction and these guys - http://machine.kerplunc.com/ . Don't know if they're any good though.

Thanks for the recommendation.

WebFaction blows me away. They are, quite simply, awesome.