Funny how things happen sometimes. We find that UPS also quit support for the old UPS calculator! We loaded the new USPS calculater and it worked with our cart version and PHP version. We can actually get sales completed through PayPal again!

To recap.... our problem was that USPS was not accepting older version of USPS rate calculator addon and a quick upgrade fixed that as well. The UPS that went out at the same time was coincidental and when beta is available for that addon we will install it as well.
Without rates PayPal can not complete and order!