Solved: Contacted Apple Support and did all the recommended fixes to no avail. Passed on to tier 2 support and found that my Apple ID was showing "Challenged". This means that parts of the iCloud platform may be restricted. Support told me that they would clear it up and in 5-8 hours things should be back to normal. YES, all is working fine now.