PART ONE of the fix:
the fix proposed by andrabr is ideal, and should help ease the problem:

/includes/modules/payment/paypalwpp.php
approx line 1778 (depending on which patch version you have installed)
change this:
Code:
      if (!isset($paypal_ec_payer_info['ship_country_code'])) $paypal_ec_payer_info['ship_country_code'] = $country1->fields['countries_iso_code_2'];
to this:
Code:
      if (!isset($paypal_ec_payer_info['ship_country_code']) || $paypal_ec_payer_info['ship_country_code'] == '') $paypal_ec_payer_info['ship_country_code'] = $country1->fields['countries_iso_code_2'];

For the technical-minded among us, the problem is that PayPal is now sending back different data, which, as andrabr suggested, was causing confusion. This fix catches that and forces the alternative lookup method to be used.