I have never used these guys personally but i see and hear good things about the service they offer

Checkout mp-hosting.co.uk you never know they might be able to save you the headache of starting from scratch, i believe there VPS based and you get full root access.

If not id be happy to help ya out just drop me a pm with ya questions, ill help with what i can