Same problem here I think. Started yesterday afternoon UK time for me. I rebooted my Airport Extreme over WAN from my work network and I haven't been able to connect it to iCloud since. Sounds like exactly the same problem. I can enter the username and password in AirPort Utility, click Sign In and it's verified - I get a green light in the status against my Apple ID, but as soon as I hit Update to store it, and go back in to check, it's amber again. I've tried everything - including a complete hardware reset and start again with the AirPort Extreme just now. Just the same. I am coming to the conclusion it must be at Apple's end.
The shared iMac connected via ethernet to the AirPort Extreme is visible in the Finder Sidebar as normal (but I can't access it via Back To My Mac from outside my local network), the AirPort Extreme isn't visible in the Finder Sidebar with it's USB disk.
Everything else works fine iCloud wise - Notes, Calendar etc, and everything connects just fine over the local network when I'm at home, except not Back To My Mac because I can't stay signed in on my AirPort Extreme, which was working until yesterday.
I have a support call booked for Saturday lunchtime. I will report back, maybe that will help you guys.