I'm having the same problem, except that for me it's always right after a restart that I can't get Messages to launch. Often if I wait a while it'll launch, but sometimes that "a while" can be several hours!
Your note @codefish46 about "firewall" got me thinking (I have no antivirus installed) so I disabled the OS X Firewall and immediately Messages launched. I then quite Messages, re-enabled the Firewall, and re-launched Messages again — and it launched. So something about disabling Firewall, even just temporarily, got it working.
I went ahead and added Messages.app to the list of apps under "Advanced" to permanently allow incoming connections, so I wonder if that will help in the future.
FWIW, the option "Automatically allow signed software to receive incoming connections" is enabled, which makes me wonder if somehow the signature on Messages is corrupt or invalid?
-Joseph