HI,
My Apple ID is from an old Dial-up Account I had and is based on the email ID I got from them
At the most recent change of the Discussion Board Software I found in my profile Page and the the Edit options on the right I could enter a different email address - and I used a Google mail one.
More recently I listed the Dial-up ID as the email for my iCloud registration which seemed to override the email setting on these discussions.
The "Portal" as I listed it above would not let me change the email to the new iCloud ID or to any other email (I was also reluctant as I use the account in iTunes and other places like iChat/Messages beta).
I was given the second link by a poster called John Galt who said it would allow me to change the email.
This worked.
It shows up on the "Portal" page as an alternative email. (there is also a big splurge notice encouraging me to consolidate the emails/IDs)
It seems linking my original Apple ID to the iCloud ID makes it one of those Apple IDs that then cannot change the Apple ID email (Apple IDs based on @mac.com and @me.com names from MobileMe cannot be changed).
As I have said the second link does allow you to change or at least enter a secondary email address that is then used by the various Apple sites/Stores that want to email you.
This should get you back to at least having the "recovery" email address reinstated.
It may well be that you have an expired @mac.com or similar @me.com address that no longer works as an Email
However you will not be able to Change the Apple ID part of this to another email.
(Seeing you seem to be getting notifications from this thread it seems you have a working email).
8:08 PM Sunday; June 17, 2012
Please, if posting Logs, do not post any Log info after the line "Binary Images for iChat"
 iMac 2.5Ghz 5i 2011 (Lion 10.7.2)
 G4/1GhzDual MDD (Leopard 10.5.8)
 MacBookPro 2Gb (Snow Leopard 10.6.8)
 Mac OS X (10.6.8),
"Limit the Logs to the Bits above Binary Images."  No, Seriously