I am having this problem too. I've tried the authentication fix posted here, but it only slightly solved the problem. There was a moment when it was working 100% when I first implemented the fix, but upon waking the computer from sleep, it was right back to the same problem.
At best, my service is in and out. Sometimes it will work for some of my iMessage contacts while not others. Sometimes it will work for only receiving messages from my iMessage contacts but unable to send. Other times, all of the contacts will show up as being "not registered with iMessage" even though they are. Then on very rare occasion it all works. I seem to have some success if I reboot, but the success will only last for as long as that session. If I wake from sleep the problem comes back.
I'm unsure if this has to do with the outages the service was having universally a few days ago. It seems like it would since prior to that time iMessage was working just fine for me. At the same time, I noticed that most everyone posting in this thread has a z77 up5 th motherboard. Is it possible that the problem might somehow be related to that piece of hardware? I thought there was a similar problem with iTunes authentication for 7-series motherboards and Ivy Bridge CPU, so is it something similar now for iMessage? Just some thoughts, but not sure.
In any case, I'm in search of a reliable fix to this problem as well.