Hmm... probably the account has been dormant, so they want to make sure that it's you that's actually making the changes?
If that's the case, it's probably going to be about the info in your account that they want to verify.
Did you also use the same browser, win account and IP when you tried this?
I have one paypal account where i get that error message......it was dormant for awhile....but others i have were also dormant and i dont have a hard time adding another email address.....i find it quite odd.