The default GoogleTalk login is on port 5223 as it is a Jabber SSL login.
However it can be made to work on port 443 (with SSL Left On)
Log out of the GoogleTalk account in the Messages > Preferences > Accounts > Google option > Account info tab
In the Server Setting Tab you can now change the port to 443
This is likely to help where the Connection to the Internet only allows default ports.
The AIM login in Messages is now on port 443 (regular posters have been saying use this since iChat 3)
It also changed the server name from iChat 6 to api.oscar.aol.com
Adium still uses the older login.oscar.aol.com In earlier versions of iChat this gained a leading "s" when using SSL
By default most domestic routers will have ports up to 1024 open (allows Web Browsing Secures logins and Mail plus FTP) - there are 65355 ports in all and some of the ports used for Logins in Messages and Video or Audio chatting are above this 1024 threshold.
I am a little surprised that the computer stayed logged in as you changed networks.
If not using SSL it is likely the AIM one was dropped and Automatically reconnected.
If the app is supposed to start when the computer does then there could be issues if the network is not established by the time Messages has finished Launching.
The fact the Bonjour Account is connecting means it is not the DNS issue.
Bonjour relies on mDSN (multicast DNS) and this in turn need DNS to be working.
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
I had this same issue occur after setting up a new network in my home and switching to it. iMessages has never had a problem connecting to Jabber or Google Talk until I switched to that new network and opened the app. It said connecting, but never succesfully completed the process. I could still message my girlfriends iPhone from my mac, but it would take longer than usual to go through and I was no longer able to see the responding bubble while someone on an apple product was messaging me back.
Anyways, in iMessages preferences, I selected the Google Talk account and tried checking "Automatically find server and port" in the server settings tab hoping it would resolve itself and had no luck. I started searching and came across this thread and tried switching the port number from 5223 to 443 and it connected instantly!
Gotta love finding an easy fix to an extremely annoying and random problem!
Thanks for the help Ralph!