Had the same issue. Here is what fixed it for me.
Finder -> Go (in the menu bar) -> Go to folder... -> type "/etc" -> Go
here, find the hosts file, now, this file is locked, I used sudo vim from Terminal to edit it, if you don't know vim, try nano, it might be easier to understand.
So, open up Terminal and type: sudo nano /etc/hosts
type in your password and press enter
delete everything EXCEPT these lines:
# Host Database
# localhost is used to configure the loopback interface
# when the system is booting. Do not change this entry.
now press CTRL+O to save, enter to confirm the path e CTRL+X to exit the program, now try Messages..
original source: https://discussions.apple.com/thread/4322695?start=0&tstart=0