Tried each suggestion, and read the article along with the extra bits and links on what's needed if not working. I even tried bringing the iPhone here and sending an iMessage to my iPod Touch with both connected to the same Wi-Fi network, no luck. Skype on the other, video works perfect without leaving the Wireless subnet.
I'm quite at a loss. No, no messages get to me and none will send, but I'm trying it with an iPhone that can both iMessage and FaceTime others beside me fine. I've tried signing out, re-signing in, checking all my credintials on my Apple ID via a web browser on my desktop too. I even changed region and back again incase it was a region issue.
I powered down between signing out and in. I even tried just killing the iMessage process (double click home and delete the process). Still no go.
I even wiped the network settings and re-did the passwords etc... for Wi-Fi, verified DNS settings. I even opened up port 5223 inbound to the iPod Touch from my DSL router (not that it should be require, the iPhone doesn't care less but tried none the less).
Okay I tried that and here's the results:
Did a restore and chose setup new device (not from backup).
Now I have a new problem, I can not sign-in at all with my Apple ID in iMessage or FacTime. But, I can sign-in with my Apple ID under Settings--> iTunes & App Stores fine. However, when I go back and try with iMessages and FaceTime, after about a minute it finally says could not sign in, Please check your network connection and try again. I can't turn iMessages off and back on, and power cycling doesn't fix it. Now it just won't sign in under those apps, but will in App store. Once signed in, in App store it still asks to sign in under iMessages.
So the situation has just gone from bad to worse by restoring the device.
I've read up elsewhere about doing a DFU recovery (not recovery mode recovery) so I might try loading old 4.3.3 firmware then re-upgrading to 6.1.3 and see if that solves anything incase there is a corrupt file or something on this. I've had it for just on a year, iMessage has never worked even when signed in. It doesn't seem to be a simple fix for something that should just work, especially after a restore to factory job.