What do you mean "delete the settings in the device" ? It's grayed out, so you can't just delete it (it's unselectable).
Do you mean the "reset all settings" choice in the General settings? I would rather not do that - there must be an easier way to change the Apple ID.
I too have this problem, and unfortuately found this thread after starting my own thread. Here is my situation:
My daughter's iPhone 4 have my Apple ID entered as the Apple ID for her iCloud account information. We want to change this to her own Apple ID, but the ID is "grayed out" and cannot be changed. I have turned off all iCloud services, rebooted the phone, and still can't change this.
As to how it got this way... my daughter tried to enter her own Apple ID after installing iOS 5, but the phone then stated that iCloud set-up failed; try again later. She then found that my ID had been entered for her. I am assuming it picked up my ID from the "Find my iphone" app - the entire family used my ID for find my iphone, so we could see each other. We turned off Find my iPhone on her phone, and still can't change the ID. She succesfully entered her own ID in the Store settings on her phone, and later upgraded to 10.7.2 and set up iCloud with her Apple ID on her computer.
I'm thinking we should do a backup and restore of her phone to see if that resets the iCloud Apple ID setting, but don't want to go through that unless someone knows it works.
Suggested new feature: the iCloud web site should have a way to monitor which devices are using an account, and provide a way to kick a device off an account.
OK - now I've got it. Go into Settings - iCloud, scroll all the way to the bottom of the screen and select the red tab "Delete Account". This kills the Apple ID entry for iCloud and you can enter the new one.
What can't be answered is why entering the correct account info at set-up failed on 3 phones so far in our family. For all 3 of these I'm having to take the "delete account" route.
If the old ID is an earlier version of your current ID, temporarily recreate the old ID by going to https://appleid.apple.com, click Manage my Apple ID and sign in with your current iCloud ID. Click edit next to the primary email account, change it back to your old email address and save the change. You can now use your current password to turn off Find My iPhone, even though it prompts you for the password for your old account ID. Then you can delete the current account, recreate your current ID again, then sign back in with it on your device. To do this, first save any photo stream photos that you wish to keep to your camera roll. When finished go to Settings>iCloud, tap Delete Account and choose Delete from My iDevice when prompted (your iCloud data will still be in iCloud). Next, go back to https://appleid.apple.com and change your primary email address and iCloud ID name back to the way it was. Now you can go to Settings>iCloud and sign in with your current iCloud ID and password.