Hmmm, when I first read your post the thing that came to my mind screaming and squirming is: you didn't get your proxies right, if you had any at all. But recently Paypal has wisened up in terms of Canadian accounts(dunno about other countries) so that really might not be the case. You can't get out of this situation with finesse, if you don't use a VCC. Just go to a site like Order page, Buy cheap VCC with Liberty Reserve look around a bit, familiarize yourself with what they offer and think about it. A code like that usually costs around 7$ and secures you a verified PP. It really depends on the ammount of money you are trying to move around, but even for a 30$ transaction 7 bucks are worth it, to make sure you will be able to spend the other 23.
P.S. And don't forget to set your proxies straight :P