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).
I was following along because I had the same iMessage problem and just today I finally got it to work. I logged out of messages and iCloud and all my Macs, both virtual and physical machines. I think it was a VM I last logged out of that got things going going again.
Best Answer
Messages always hang on my Mac as well, error telling me no account set up etc, and restarting my Mac always helps to bring it back to normal.