They're based in Bluesquare and rent from Poundhost. They were having some problems with connectivity to customers on Virgin Media - not sure if this is resolved yet but there was a long thread on their forums about it.
They seem to have pretty responsive sales and support though, from what i've heard.
I bought a VPS from them a year or two back, to use for some monitoring services (usually what I use VPS' for) and application testing. Unfortunately my experience was not very good, with a horrible uptime and performance. The support response time and quality was not great either. I decided to leave them in the end, as it was not worth the fairly high monthly fees for me.
That said, I know others who's been with eukhost for a long time without significant problems - so my case might just have been an exception, or they might have restructured/improved themselves over time.