oops!
Sounds like they messed up here.
I've used Streamline.Net dedicated servers and they have been excellent. They have a hardware raid controller so disk failures do not cause any problems.
I've also heard good things about rackspace, but I think they are quite expensive.
I've chosen Paris as her servers go down when ever you want them to.