I've been in detailed discussions with Apple about this for a few weeks now and finally a solution has been found.
Problem description:
Mac fails to log in to Messages, FaceTime and App Store, with an error such as "an unknown error occurred". All other logins and iCloud functionality is normal - only these three items are affected.
Solution:
There is a known issue in which the Mac may fail to log in to the App Store if there is no "en0" Ethernet port present. I know it sounds weird but it is a fact. It can happen (not sure how) that a computer ends up with no "en0" assigned, which was my case - my WiFi had somehow become assigned to "en3" and no "en0" was present. Once this en0 issue is resolved, the App Store magically works again - and I found that the login issue with Messages and FaceTime was likewise resolved at the same time.
To resolve this issue, delete WiFi plist files in /Library/Preferences/SystemConfiguration. (Note this is at the System level, not at the User level). You can find the how-to with a Google search. Then reboot, whereupon the rebuilt plist file will properly assign en0. After that all these logins should start working again.
To find out what Ethernet port your WiFi is assigned to, go to Apple logo - About This Mac - System Report - Network/WiFi.
Hopes this helps somebody. It worked for me!