I never used this carrier, but the messages is added here:

/app/code/core/Mage/XmlConnect/Block/Cart/Paypal/Mecl/Shippingmethods.php:71

So the question is, why is $groups == false?

$groups = $this->getShippingRateGroups();
if ($groups) {
    // ...
} else {
    $message = $this->_quote->isVirtual() ? $this->__('No shipping method required.')
        : $this->__('Sorry, no quotes are available for this order at this time.');
        $methodListXmlObj->addCustomChild('method', null, array('label' => $message));
}

There is only one place I can find where the ShippingRateGroups is set:

/app/code/core/Mage/Paypal/Block/Express/Review.php:216

I searched for setShippingRateGroups() and Shipping_Rate_Groups

This value is somewhere loaded and set implicit. Good luck with the debugging.

I used the following code in my ../template/checkout/onepage/shipping_method/available.phtml custom theme template inside the foreach shippingrategroups loop....

USPS and additional shipping methods must be enabled. It forces any APO address to USPS if it finds a city or region code that matches.

         <?php //Added to force USPS for APO
            $address = $this->getAddress();
            $apoStateCodes = array("AE", "AE", "AP");
            $apoCityCodes = array("APO", "FPO", "DPO");

            $regionCode = Mage::getModel('directory/region')->load($address->getRegionId())->getCode();

            $carrierName = strtoupper(str_replace(" ", "", $this->getCarrierName($code)));
            if (in_array($regionCode, $apoStateCodes) || in_array($address->getCity(), $apoCityCodes))
            {
                // IT IS APO, so skip iteration of non-USPS
                if ($carrierName != "USPS")
                {
                    continue;
                }
            }
            else
            {
                // ITS A NORMAL ADDRESS
                if ($carrierName == "USPS")
                {
                    continue;
                }
            }

            /* OLD WAY OF DOING THINGS (only works on PO box)
            if (preg_match("/p\.* *o\.* *box/i", $this->htmlEscape($this->getAddress()->getStreet(1))))
            {
                $carrierName = strtoupper(str_replace(" ", "", $this->getCarrierName($code)));
                if ($carrierName != "UNITEDSTATESPOSTALSERVICE")
                {
                    continue;
                }
            }
            */
         ?>