I have seen one definite issue with this that has been identified.
When Computer have been refurbished or repaired the Serial Number goes missing. (I was under the impression that Apple Store and other validated centers were supposed to flash the detail back to the Motherboard).
Some app use these details to increase the security around signing in.
If you have not got the right details it fails.
You can try Quitting IMAgent in the Activity Monitor and then relaunch Messages as this sometimes works.
Also Adding a Public DNS servers to your Network Settings seems to help (System Preference > Network > Advanced Button > DNS tab)
Google run 22.214.171.124 and 126.96.36.199 but there are others if you search.
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