I got the same message and logged into my paypal using www.paypal.com and found the address was not added. If you click on their link but did not enter your info, they now have your email address as a good one and the amount of spam you will get will sky rocket. It happened to me last year.
Mike