I had a similar problem, with the culprit being that iCloud got confused, and continued to send text messages as iMessages, so that my new phone (non-iphone) never got them.
Turns out, in order to turn off iMessages settings, you must disable iMessage EVERYWHERE. If you turn off iMessages on a phone, and leave it on your iPad, it won't reset (this was my issue).
So, I suggest you try this: iDevices (all of them): Settings>Messages. Turn off Messages. (on your iPhone, you can turn on sms message so at least you still get texts). On Macs, remove any accounts in iMessages by clicking '-' by them in the account preferences.
Make sure you have de-registered on ALL your devices. Give it an hour or so. Then create accounts on messages on the devices using your Apple ID. See if it works.
If this does not work, call AppleCare. I found that if you go to the AppleCare link in the website, it warns that it will charge you $$ per min for help if you don't have an AppleCare plan. Call the number anyway, agree to whatever. When I called, Apple did not charge me for the iMessages issue, as it is a known issue. (mine was slightly different, I will admit).
Best Answer
Restart your computer. That solved it for me.