Paypal is safe, just watch out for all the bogus phishing emails you are likely to get. Just use common sense about it and you will be fine. Paypal says they will never ask you to provide any account information via e-mail. Also, never follow any links provided in any e-mails.
In direct contrast to this statement, while you verify your account, they will post 2 small deposits into your account, you have to get your statement and tell them the amounts to verify your account. It's no big deal but when I did it years ago, I seem to remember getting an e-mail with a link to login and enter this info.
I'd bet they have changed this procedure to reflect the new security policies.