New IOS7 configured with wrong Apple ID
I had this exact issue after updating to iOS 7 an hour or so ago.  The ultimate resolution, although it took me an embarrassingly long time to arrive at, was to log in using my current Apple ID password, ignoring the out-of-date apple ID, while attempting to delete the iCloud association (as you are already attempting to do).

A couple of things that I had done in the mean time that might have helped things along unexpectedly:


I logged into icloud.apple.com using my current credentials.
I logged into appleid.apple.com and added a (heretofore) missing year to my Date of Birth.


I sincerely doubt either of these changes had any impact, but I thought I'd mention them in case you want something to try if your current password does not work.