Maybe they meant your address wasn't confirmed with PayPal?
You *can* have an address that is Unconfirmed, but one of PayPals 'rules' is seller MUST ship to a confirmed address only.
At paypal go to My Account --> Profile
Click street address.
Is your address correct and status say confirmed?