I upgraded from Mountain Lion 10.8.2 to Mavericks 10.9.0, & then up to 10.9.4 the other day. Using Chameleon 2.2svn bootloader. (My SMBIOS.plist & serial number were changed during this).
My iMessage App had been working for well over a year on Mountain Lion without any issues, since I applied the Modules / FileNVRAM fix, and I knew upgrading to Mavericks would require a reapplication of the fix.
But I've since had trouble trying to get it working again now. And along with everyone else, I'd tried absolutely
everything, short of attempting Clover bootloader or actually calling Apple.
So about 15 minutes ago, I decided to give it a shot & call their support (Apple Care Australia, 1300-321-456).
The assistant asked for my first & last name, & a phone number in-case the call is disconnected.
He then asked what the problem was, to which I advised that my Messages App was no longer working on my "Mac". I provided the Customer Code which was showing in the Messages log-in error window.
He asked for the serial number of my Mac, & I read out what was listed in my SMBIOS.plist.
It took him a moment, but then he asked me to reconfirm the serial. And then reported that for some reason, it wasn't showing on the system.
He asked me for my email address, & then shortly after asked to confirm that it was a Mac I was calling about, & not my MacBook Pro, which he did have listed. I confirmed that it was a 2008 Mac Pro, and that the Messages App hadn't been working properly for a couple of weeks now & won't let me sign in, even though I know that I am using the correct username & password.
He said that he knows another work-around, & put me on hold for about 4 - 5 minutes.
When he answered again, he advised that he'd done everything that he needed to do on his end, & asked me to try login again.
Sure enough, I logged in straight away!
I sent a few messages to confirm that it was working, then restarted, & everything appears to be fine!
Huge thanks to jaymonkey & everyone who contributed to the original post / guide!