I have been suffering with the loss of iMessage on my iPod Touch 4th gen, 3Gs, 4s and my 5, all running iOS6 but I think I may have cracked it, only time will tell.
In Settings > General > Date & Time
I had 'Set Automatically' switched to 'ON' but 'Time Zone' was showing the spinning pinwheel.
I realised that in Settings > Privacy > Location Services > System Services
I had 'Setting Time Zone' switched to 'OFF'
This I assume was causing the 'Time Zone' to be unable to update, thus causing the spinning pinwheel.
If I switched 'Setting Time Zone' to 'ON' I noticed that 'Time Zone' did update to my current time zone but only if there was either a network connection or WiFi connection, seems quite obvious.
After doing this I done a hard reset on my device.
After the device rebooted I went to Settings > Messsages
And turned iMessage 'OFF' then 'ON' again and waited for it to activate.
Once iMessage activated, I was able to send and receive iMessages.
I hadn't finished though, something struck me in the relationship between iMessage and the 'Time Zone' setting.
I went back into Settings > Privacy > Location Services > System Services and turned 'Setting Time Zone' back to 'OFF'
This initially didn't seem to effect the use of iMessage and looking in Settings > General > Date & Time showed my location in 'Time Zone'
At this point I made sure that WiFi was turned off on my device and then switched Airplane mode to 'ON' for a brief period and then 'OFF' again and waited to get network reception.
I now tried to send an iMessage but had no joy, there were no blue speech bubbles next to contacts names and the 'SEND' button was green indicating SMS Only.
Again I had a look at Settings > General > Date & Time and noticed straight away that 'Time Zone' was showing the spinning pinwheel once again.
Now the reason I had turned 'OFF' 'Setting Time Zone' in Settings > Privacy > Location Services > System Services was that I had heard various reports of it consuming vasts amounts of battery power and also because I didn't really see a use for it.
Now what I did was to go to Settings > General > Date & Time and change 'Set Automatically' to 'OFF'
I again checked iMessage by attempting to send a text, hey presto it was back up and running and relevent contacts had the blue speech bubble.
I held back my excitement for a while and tried a few things first.
I made sure once again that WiFi was off on my device then again turned Airplane mode on, left it for a minute and then turned Airplane mode back to off. Once my network had been found I tried to send a text and yes, it sent as an iMessage and my contacts that had iDevices showed the blue speech bubbles.
Well, I thought that it could be this easy to solve so I did another hard reset on my device, waited for it to reboot and connect to my network.
Then I thought I would try to send an iMessage and opened the Messages app, started to type a known iDevice contacts name, initially the name appeared but without the blue speech bubble so I cancelled the message, closed the Messages app and then tried to do the same again, this time success, blue speech bubble next to contacts name and I was able to send an iMessage without a hitch.
Just to clarify, I have got 'Cellular Data' switched to 'ON'
So to me, for some reason iMessage is linked to it's ability to locate the 'Time Zone' that the iDevice is in and from my experience as laid out above, if the 'Time Zone' is unavailable then iMessage will also become unavailable.
Hopefully this information will help others in a similar position.
regards..,