I had exactly this problem yesterday, both on my iPhone 4 (which had been working on iMessage for months) and on my wife's iPhone 3GS. I spent an hour on the phone to Apple support, but they couldn’t fix it. All they could suggest was an appointment at an Apple store. Thanks to the suggestion above of using Google's DNS server (8.8.8.8), I managed to fix it on both iPhones.
Using my own proxy server, I found the servers that the iPhone connects to when activating iMessage. There are several, but two of them are deployed regionally with the same hostname but multiple IP addresses (and consequently multiple servers). I am in the UK and when I do DNS lookups, I get the following results:
init.ess.apple.com
82.96.58.9 from a UK DNS server
63.80.4.41 from Google's US DNS server at 8.8.8.8
static.ess.apple.com
82.96.58.47 from a UK DNS server
80.239.148.162 from Google's US DNS server at 8.8.8.8
The regional differences in DNS resolution are because Apple uses Akamai Technologies to deploy local points of presence, which are intended to reduce latency and intercontinental bandwidth. Therefore your iPhone does a DNS lookup on the hostname and a regional IP address is returned. UK DNS servers return the above 82.96.58.* addresses in Sweden; Google's US DNS server returns the above servers in the US, which I am guessing are Apple's primary iMessage servers. The Swedish iMessage servers seem to be deficient in some way, which is why you sometimes get this problem when activating iMessage outside the US.
After changing the DNS for your wifi connection to 8.8.8.8, you may need to restart your iPhone before trying to switch on iMessage again, as restarting will flush the iPhone's DNS cache. Otherwise your iPhone will retain the previous DNS mapping to regional Apple servers rather than to the more reliable primary Apple servers in the US.