I use Gandi[1], they have both IaaS and PaaS offers. They are based in France with a datacenter near Paris. They have a very good support team and I'm happy with the service so far.
There are been rumors that they might became an settle over to the states, but to the current day the are located in France (and I doubt this will change).
I can really recommend them, if you are looking for some "cloudy" servers (dynamic resources, etc.)