How do I update the primary email address used by my Apple ID when using Find My iDevice? I have an Apple ID that I use for both the App/iTunes Stores and for iCloud. Because I originally created it years ago, it's an email address I no longer use, let's call it dan@old.com. I would like to replace it with dan@new.com. 

This is easy enough to do from the Manage My Apple ID web interface, however when I change the address and attempt to update my iPhone and iPad I hit a snag: in order to Sign Out of my Apple ID in iCloud Settings, I must first provide my Find My iDevice credentials, since that prevents a thief from simply punting me out of my device were they to steal it. 

The problem is, it asks for the Apple ID password for dan@old.com, and when I enter that, it fails (with the incredibly helpful message "there was a server error"). I have to assume this failure is because that combination of email address and password is no longer part of my Apple ID.

Can someone provide me with a sane, step-by-step way to change my primary Apple ID email address from one email that I control to another, given the use of iCloud and Find My iDevice on multiple devices?
As Tyson says, this might help: http://support.apple.com/kb/ts5223

If you can make your AppleID change back to dan@old.com you should then be able to sign out of it on the iDevices. After signing out the iDevices - change the AppleID again to dan@new.com and you're good to go.

The place to change your AppleID (which is used by iCloud and iTunes and the Mac App Store) information is at https://appleid.apple.com/