I actually had this problem even though I had iCloud enabled since day it went go live. I woke up two days ago to find that my account was basically reset somehow and I would never receive my verification email.
I figured out a workaround by logging into my Apple ID at
http://appleid.apple.com and on that page it said to verify that my email account was what was attached to my Apple ID. Interesting enough, my Apple ID was my email account (which it had been for a long time) and its the only email that has ever been associated with it. I clicked the Verify button and viola, everything worked again.
Hope this helps.