Okay, so I've narrowed down the issue a bit more...

If the customer forgoes setting up a user account in ZC, and doesn't have a Paypal account (using PayPal's IPN module), we enter all their information (with a billing address in Venezuela and cc info...) and hit 'continue' (from within paypal...)

It drops us back into the ZC site, with the following error:

Not Available At This Time
Sorry, we are not shipping to your region at this time.
Please contact us for alternate arrangements.

Is this a PayPal issue? How can I address this?