Hi,
This does seem to be an odd one.
When the Messages Beta came out ot seemed that some people's Macs could not find the iMessages server and hence the suggestion to add Public DNS servers to the Network Settings.
Then it seemed that the support app - IMAgent - was the issues and needed to be Quit in the Activity Monitor.
It starts up in the background when the Mac starts up and does not have an icon on the DOCK. Using the Activity Monitor is the only way to Stop it running outside of shutting the Mac down.
We have also tried deleting the various .plists involved with IMAgent, the com.apple.imservice.iMessages and the imessage.bag one.
This has worked for some (On restarting Messages) for some but not for others.
More recently we have tried removing the Apple ID for the iOS devices and the Mac App in an effort to "Start Again".
By now people will have normally posted back enough times for a judgement to be made as to what seems to be working the best.
Some claim to have tried deleting the Apple ID from the Messages app on the Mac then the iPhone plus all the .plists with ichat, imagent and iMessages in them, then stopping the IAMgent from running in the Activity Monitor on the Mac and then starting the app again.
I would remove the Apple ID from the Messages app on the Mac.
Shut down the App
I would enter ~/Library/Preferences in the Finder > Go Menu > Go to Folder in the dialgue box box that appears.
Remove the following
Anything with com.apple.ichat. .plist in the name
The com.apple.imagent.plist
The com.appple.imservice.imessage.plist
The com.apple.imessage.bag.plist
Then I would open the Activity Monitor and Quit IMAgent.
I would follow this be removing the Apple ID from all iOS devices followed by turning the devices Off (or putting in to Airplane mode for at least 5 minutes).
I would then try adding the Apple ID to an iPhone first..
If that seems to get Accepted I would start up the Messages app on the Mac and add the Apple ID there.
8:10 PM Wednesday; October 17, 2012
Please, if posting Logs, do not post any Log info after the line "Binary Images for iChat"
iMac 2.5Ghz 5i 2011 (Mountain Lion 10.8.2)
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