This is a completely legitimate request. I had this happen a while back and it is a total pain in the butt but you have to do it to get access to your funds. Unfortunately there is no way around it.
Just make sure that you go directly to the paypal website/contact info when you provide them with the info!
Just make sure that you go directly to the paypal website/contact info when you provide them with the info!