Yeah, I had Paypal call me once too. Actually I called them. Paypal actually hires out this security service, so it isn't really Paypal calling you, it's a third party security service. For some strange reason, this service wasn't allowed to phone outside the U.S., so when my number came up for the spot check, they said "non U.S. phone number" and they cut off access to my Paypal card. I didn't think much of it when it got declined one time, because I hardly used the card anyway, and to be honest, the card has been flukey for me from the start (it's hard to find places in Canada that accept it). My account still worked fine so I forgot about it. A month or two passed and finally the security service wound up emailing me and they asked me to call them and we straightened things out and they reactivated my card (they couldn't believe that I hadn't freaked out with no card access for that long).
Mike's theory that Palisades got redflagged from all the Paypal payments incoming sounds right to me though.