I've been getting the same error message. I run the latest version of ZC, and applied the patch. I've turned on the PayPal log, and this is what I got:

Code:
Redirecting to checkout_shipping - Stack: checkout_shipping
Message: We were not able to process your order. Please try again, select an
alternate payment method, or contact the store owner for assistance.
(Shipping Address Country Empty)
Session Data: Array
(
    [customers_host_address] => d5123.telenet.be
    [cartID] => 45773
    [cart] => shoppingCart Object
        (
            [contents] => Array
                (
                    [120] => Array
                        (
                            [qty] => 2
                        )

                )

            [total] => 0.02
            [weight] => 0
            [cartID] => 45773
            [content_type] => physical
            [free_shipping_item] => 0
            [free_shipping_weight] => 0
            [free_shipping_price] => 0
            [observers] => Array
                (
                )

        )

    [navigation] => navigationHistory Object
        (
            [path] => Array
                (
                    [0] => Array
                        (
                            [page] => index
                            [mode] => NONSSL
                            [get] => Array
                                (
                                    [type] => ec
                                    [token] => EC-XXXXXXXXXXXX
                                    [PayerID] => 9TTXXXXXXXX
                                )

                            [post] => Array
                                (
                                )

                        )

                    [1] => Array
                        (
                            [page] => checkout_process
                            [mode] => NONSSL
                            [get] =>
                            [post] => Array
                                (
                                )

                        )

                )

            [snapshot] => Array
                (
                )

            [observers] => Array
                (
                )

        )

    [check_valid] => true
    [language] => dutch
    [languages_id] => 45
    [languages_code] => nl
    [currency] => EUR
    [updateExpirations] => 1
    [session_counter] => 1
    [customers_ip_address] => 84.193.151.00
    [new_products_id_in_cart] =>
    [valid_to_checkout] => 1
    [cart_errors] =>
    [payment] => paypalwpp
    [customer_id] => 48
    [customer_default_address_id] => 55
    [customer_first_name] => Dave
    [customer_country_id] => 21
    [customer_zone_id] => 0
    [sendto] => 55
    [billto] => 55
    [cot_gv] => 0.00
    [shipping] => Array
        (
            [id] => zones_zones
            [title] => Tariefzones (Verzenden naar: BE)
            [cost] => 2.4711
        )

    [comments] =>
    [messageToStack] => Array
        (
            [0] => Array
                (
                    [class] => checkout_shipping
                    [text] => We were not able to process your order. Please
try again, select an alternate payment method, or contact the store owner
for assistance. (Shipping Address Country Empty)
                    [type] => error
                )

        )

)
Any idea on what I should try next? Thanks for helping me out