HI,
iMessages does not use iCloud.
It is like iTunes in that it logs in with your Apple ID and it's password.
It is true that the same Apple ID and password may also be your iCloud ID.
Therefore logging in to iCloud in a Web Browser actually tells us nothing about the iMessages login which is on a completely different server and in fact is separate from the FaceTime one.
Since issues with Messages 7 (Mavericks in Messages 8) I have had two public DNS servers listed in System Preferences > Network > Advanced Tab > DNS
The two I use are 8.8.4.4 and 8.8.8.8 which belong to Google.
Check the Date and Time and Zone settings on the Mac.
Make sure the router is also set to the same Time Zone and has the correct Date and Time.
Double check the Firewall on the Mac.
System Preferences > Security and Privacy > Firewall tab
If On check the Option button
Signed Software should be allowed and Messages and iMessages plus FaceTime needs to accept incoming data and be in the list.
Try a different Mac User account if you have one.
and use Messages there with the details you normally use.
8:23 pm Monday; October 28, 2013
iMac 2.5Ghz 5i 2011 (Mavericks 10.9)
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