I've tried every suggestion I could find on Apple forums. Deleted .plist files, removed message caches, reset passwords, coordinated sign on/offs between my iPhone and my Macs, reset iPhone and reinstalled Mavericks on my Macbook Air. All pointless exercises.
I suspect it all started because I jailbroke my iPhone using Pangu. It may or may not have been the culprit, but my problems started a couple of days after I did it. All my phone conversations went green and stopped synchronizing with Messages apps on my Macs. Trying to send a new message from Macs would result in either "Your message could not be sent" error with a warning icon next to it, or:
XXX is not registered with iMessage.
So I restored my iPhone to factory defaults using iTunes. That didn't help immediately, but in a day or two, my conversations with other iPhone users went blue. So I am happy that works.
So now I sacrificed my Macbook Air to try and make messages work on it. I reinstalled Mavericks several times, each time trying different approaches: not immediately signing into iCloud, not associating an iCloud profile with login profile, etc. Nothing helps. I launch Messages app, it asks me to sign in (and I do, successfully), and then nothing goes through.
Sending messages to myself also works inconsistently. Yesterday, whatever I sent to myself (using phone number) would appear delivered to the same window, but not on my phone. Today I get "… not registered with iMessage" error.
Best Answer
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).