iCloud email - server password changed?
I just contacted Apple Support and they confirmed this was a new Apple ID authentication issue. Basically, iCloud has deemed that my account should not just have one password, but a dual-verification which, once completed, generates app-specific passwords for each device used (Apple devices or not).


Two-step verification for Apple ID 
Using app-specific passwords