My original Apple ID was associated with an email address that is not valid anymore. I updated my Apple ID to a real valid email. I managed to update it successfully with everything except iCloud on my phone. The App Store, iTunes, and everything else on my phone has the correct ID except iCloud.
When I try to delete my iCloud account from Setting > iCloud > Delete Account, I am asked to enter my password for the old email address, when I do so, I get a reply that the password is wrong. When I try to retrieve it, I am asked for my date of birth, and then told that it is also wrong.
How can I change to my new Apple ID?