This issue has me crying over and over, because since I changed my iCloud Password some 5 weeks ago, Messages haven't come up on either my MBP or iMac. I had other iCloud issue when I first changed it, and they have sorted themselves out, but for the life of me, I haven't got Messages to work !!!
Signing in/out of iCloud, restarting on so on.
What gets me, is nothing was changed apart from my iCloud Password, and I have given up for now.