You're severely mistaken. Using a VPN is a pretty smart move when you access your paypal account in a coffee shop on WiFi. I always use my VPN when I'm logging on to sensitive accounts (FB, Google, bank or corporate network) in public locations (hotels, airports, coffee shops). In fact, my company demands it.
I do wonder which VPN the OP used. If he use one of those anonimizing VPNs that is popular with bittorrent downloaders, spammers and the like, then he shouldn't be surprised if Paypal's fraud detection unit was suspicious.
Feel we're not getting the whole story here.