What seems to be the issue, and have you given them chance to fix it? Having recently migrated ~80 sites to Nimbus with 0 problems (and any issues that were encountered were quickly resolved) id say give them chance to look into the issue and fix it
Sometimes asking for input elsewhere may lead to guidance that can be relayed to them that allows them to find something that they may have overlooked. Recently participated in a thread involving OrangeHost that ended up that input from the community revealed that they (OrangeHost) had made some caching changes to their HTTP servers for their shared hosting service that was causing a negative impact on their clients forums - and that they had overlooked that.
A) That's not managed, which the OP asked for
B) It's a virtual machine, not a 'ready to go' hosting service.
c) Someone who needs management will likely need a control panel, and the free options are terrible (putting it mildly), so add a minimum of $5 a month for DirectAdmin or ~$15 a month for cPanel on top of it, and DigitalOcean's no longer a decent option.
OP - avoid any of the UK2 group hosting provders if you can, and any owned by the EIG group. Both of these companies have a tendancy to provide pretty lackluster support and severely limit server resources on most, if not all of their hosting plans.
EIG will need some research. To give you an idea, they own HostGator, BlueHost, GoDaddy, etc. Their wikipedia entry lists some of the companies they own, but not all of them.
My personal recommendation for a fully managed, and extremely reliable UK host would be Clook. I've not used them in about 3 years (no longer needed any managed hosting, so left to reduce costs) but know of people that are still with them. Their support is top quality and the hardware they use is amazingly reliable. Jim and co have been running it for years and have only ever focused on a premium line of hosting packages, and the difference is very evident when compared to the likes of eUKHost for example.