Hi,
This issue does seem to be now limited to OS X 10.8.4 updates and seems to relate to something about IMAgent.
This can be solved by Shutting down Messages and opening Activity Monitor (Applications/Utilities) and finding the entry for imagent (Lower case and no icon)
Highlight the item and use the Quit option top left and confirm Force Quit.
Restart Messages.
Whilst you may have seen imagent restart itself in the Activity Monitor this seems to "clear it" for Messages.
This does presume that you have already had Messages and FaceTime working since OS X 10.8.2 when the Serial Number issue came to the fore.
If you have a computer that you have updated straight to OS X 10.8.4 and missed out earlier versions then check the Serial Number show up.
Open System Info (Hold the ALT key whilst using the Apple Icon menu
Or open About this Mac in the Apple Icon Menu and clicking twice on the current OS level line (It will change to the Build Number (a count for the OS level again) and then to the Serial Number).
It can be missing if the logic board has been replaced in a repair or refurbishment.
It needs to be "Flashed" back to the board at an Apple Store or Apple Authorised Service Provider.
9:19 pm Friday; August 9, 2013
iMac 2.5Ghz 5i 2011 (Mountain Lion 10.8.4)
G4/1GhzDual MDD (Leopard 10.5.8)
MacBookPro 2Gb (Snow Leopard 10.6.8)
Mac OS X (10.6.8),
Couple of iPhones and an iPad
"Limit the Logs to the Bits above Binary Images." No, Seriously