Have you try to setup new user account and see if this is also happening?
Boot to safe mode (turn on computer and imiedietly press and hold shift button and release only when on the screen will be apple logo and progress bar underneath) and try again.
If you have any Adobe apps like Photoshop, Elements etc. they tend to add lines to /etc/hosts file and this can cause the problem that you have it.
You can check your hosts file by running this in terminal:
I think it was a firewall/crappy connection that was affecting my sign-in. I think Messages uses a different port for sign-in, and it was probably being stopped by some over-agressive DSL firewall...
Now that I'm at the university in Austria, the connection is so much better! Still trying to hammer out why the DNS server will just randomly stop resolving URL's, maybe changing to Google's Europe dns server will help with that.
Thanks for your help!