You need to change your actual @icloud.com email address, or you need to change the email address associated with the AppleID your iCloud account is created under?
If the latter, log in at http://appleid.apple.com/
I do have a new apple ID which I can access but for some reason when I log in to the computer every time it pops up a box to type in a password for this OLD apple ID. I no longer have this account/email and I don't know the password, it won't accept any of my old ones. I think it is associated to an old facebook account and my contact list. It appears that if I try to totally delete old ID, it will delete all my contacts, photos, calendars, etc. This is driving me nuts as it is really messing up my icloud. I think since I've deleted the facebook account that is why it won't accept any passwords (I've tried all old ones for this account). When I go thru icloud to change the password, I can't send an email because that email account no longer exists. The other option to put in your birthdate which it also won't accept. Any ideas????