Just saw this solved in another thread - you have to go on iCloud.com, click on your profile, and then your apple ID, and it'll pop the Apple ID management site - you need to set the password to something that contains at least 1 capital letter and 1 numeral, then it's working fine. The initial setup allowed us to use our old weak-sauce passwords to connect up things, but they are nudging us toward a slightly better security.