I had this problem on my macbook pro 10.9.5 today in March 2015. After a frustrating 2 hrs, it seemed to boil down to this: If you have two-step verification for iCloud (4 digit code to your phone to sign in), then Apple is now requiring an "app specific password" for iMessage and FaceTime , since those applications don't use two step verification. I found this out by going to Message and trying to turn on the iMessage account .. after several unsuccessful tries using my iCloud AppleID password I finally got prompted to go to get the app-specific password at iCloud online, It's 16 digits generated by Apple that are for both FaceTime and iMessage ... and it worked. But I got so annoyed, I just went into iCloud settings online and turned off two-step verification - which also ended the requirement for the app specific password for FaceTime and iMessage.
Apple software has become almost as opaque and non-inuitive as Microsoft's. If this app-specific pass is suddenly a new requirement, why wouldn't Apple send out a broadcast email to everyone using 2-step verification?