Ok it seems that they are no longer allowing us to change the e-mail address ourselves. I had a chat with Origin's live chat and here is what was said:
you:
I am trying to update the e-mail address on my origin account
you:
am I able to do that?
Sharat: Actually that option is not available on players end any more, however you can verify the account to me so that I can change that for you. May I have your email ID that you have registered on EA?
So to change your e-mail in the future you will need to login to your origin account here:
https://www.origin.com/us/login then click on support and after saying it is an Origin Account Management question chose live support.
I had to answer the security question on the Origin account to change the e-mail addres.s
Good luck all.