Have a look at services from a2hosting.com and libertyvps.net.
They have always been wonderful service providers. Even with thorny issues they seem to work quickly and efficiently to get them resolved to your satisfaction.