Is that still the case?
AWS networking continues to kind of suck; Google probably does at least that part better.
Other options might be Rackspace, Windows Azure (I think you can run Linux VMs, however I dont know how well that's working) or Google Compute Engine (rather new, so YMMV). Those are probably the biggest players in the cloud market.
This was before OpenStack, but trying to get information out of Rackspace about what's changed is like trying to get a Republican to vote Democrat.