Recommend a Xen Based VPS

First, I don't really understand what you mean by zen-based vps. But if you're looking for some solid services, here're my 2 cents...

Test response times and download speeds if possible.
I have an account with Linode. They do offer Ubuntu 8.04 and are less expensive than Slicehost and the user community is at least as great (if that matters anyway)
You can choose Newark, NJ as your DC -- this is the closest link you can get from the US.

A friend of mine administers a couple of VPSes which are hosted at Xtraordinary. He's more than satisfied with the performance and reliability of their service but this is strictly his opinion -- I haven't done business with them yet. They seem to look less expensive compared to Linode (esp. when looking for a larger plan)

I use VPSLink(http://vpslink.com/vps-hosting/) for few Drupal based sites
I recommend Link-3 as minimum for Drupal, I have test with Link-2 - it work with Drupal, but ... it is enough for few users only.

@melon - may be Alan mean Xen

Both Slicehost and Rimuhosting (at least their US ones) are good choices. They have rock solid servers, and great support. We have used both of them for clients.

Regarding the latency from Ireland to Slicehost (St. Louis Missouri), I measured it and the difference is not major. Pings take 50 ms from Southern Ontario to St. Louis, while from Ireland to St. Louis it takes 113 ms. So 63 ms for the Atlantic is not bad, given the laws of physics and all.

I find http://www.xtrahost.co.uk/xenvps/ are excellent.

I've used RimuHosting before and they are very good.

Their hosts here in Australia are a little expensive though, but I recently put a client on Crucial Paradigm and find them very good too:

http://www.crucial.com.au/

I'm really happy with Linode.com running Ubuntu Server 8.04. When you sign-up you can choose which datacenter facility you want. There're 4 locations. The closest one to you is Newark, NJ on the Atlantic coast. Read more at http://www.linode.com/avail.cfm

Test Linode performance with the first comment at http://www.linode.com/forums/viewtopic.php?t=2636

Vote for a Linode datacenter in Europe http://www.linode.com/forums/viewtopic.php?t=3307

These days I use and recommend Slicehost, Linode, RimuHosting and SoftLayer. I've also been playing around with ChunkHost, which is currently free but has no track record in terms of customer support or long-term reliability as far as I can tell.

Slicehost is somewhere in the middle in terms of price and has always been rock solid. They were also sponsors of DrupalCamp LA 2009 and the Drupal Design Camp in Boston. I recently gave one of the founders a hard time about their prices and was told that their prices may be changing soon.

Linode is the cheapest and I've been very happy with them. My guess is that they're probably the right webhost for you.

Rimu costs more than Linode and Slicehost but the thing is that their support is simply outstanding. It's so good that I can't tell the difference between their technical support and customer support. Every question has been answered within minutes and always includes the details I need. If you can afford it, go with Rimu.

SoftLayer starts at $99 a month and therefore costs the most but it's the cheapest in the long run if you need a lot of additional IPs, tons of storage or things like a CDN or transcoding service. The speed of their network has to be seen to believed. I did a speed test a few months ago and SoftLayer's network was 10x faster than Linode and Rimu, who have data centers in the same city I was testing.

An important thing to consider is that Linode, Rimu and SoftLayer offer 32- and 64-bit architectures while Slicehost only has 64-bit. To make your money go further, it might make sense to get a 32-bit system because the memory usage will be somewhat lower.

I'll throw in my hat by saying that I've been a pretty happy customer of Linode too.

I've also heard very good things about Slicehost.

-- Doug