MacOS – iCloud Services (iMessages/FaceTime/Continuity) Very Broken on the Mac

I'm having the most frustrating problem with iCloud on one of my Macs. Firstly, the Mac (a late 2012 iMac) was working flawlessly with all iCloud services up until a few days ago. Now, I am able to login to iCloud in my OS X user account fine, but no messages are ever displayed, no continuity features work, Messages will not send (some users show as not being registered with iMessages, some the message simply fails to send, and if I text myself I see the iMessage on that Mac only), FaceTime tries to dial but never completes, etc. This happens on all user accounts with all iCloud accounts on this Mac, not just mine. The same iCloud account works fine on a different computer (MacBook Air) and an iPhone running newest version of iOS 8.

I'm not at all sure if it's related, but I created a Mavericks VM in VMWare Fusion and signed in to iMessages on that VM on the iMac just before the time it started having issues, which worked and continues to work fine (the VM running on the "broken" iMac).

Here are some things that I've tried:

• reset the PRAM (many times!)
• reinstalled the OS (did not clear the drive first – didn't want to lose my stuff, that's next step. and also it seems insane)
• updated to 10.10.2 beta (this somehow got Messages to start sending SMS (although it is not enabled to do so on my iPhone!) messages but it is otherwise still broken)
• changed iCloud password to force all devices signed into account to sign out
• ensured that serial number shows in About This Mac
• changed my DNS records to google's, 8.8.8.8, 8.8.4.4
• tried other iCloud accounts
• turned the computer off for a few hours
• deleted ~/Library/Preferences/ directory and ~/Library/Messages/ directory to force full data reset of Messages app and iCloud preferences, then rebooted, but seems silly since all other users are having issues
• left iCloud logged out for a few hours and logged back in

Any help or suggestions is greatly appreciated it. I'm torn between calling Apple support (since the computer is out of AppleCare) and reformatting the computer to try to fix it.

edit: Mac has been connected to the network via WiFi and ethernet since problems began, no difference on either networks. Other Macs and iOS devices working fine on the network, and the network works great for all non-iCloud related stuff. I can go online, send files over network, etc. No issues.