Thanks to all who contributed to this thread. It's a lifesaver.

It appears as if different installations works differently on this issue. In my case, each of the fixes worked individually, and they both worked together. I kept ParsonsMT's "title" fix as it seemed cleaner to me, and returned DrByte's version back to the Standard line. The shipping estimator works, and the FedEx shipping options appear on the checkout_shipping page (which it didn't at first until I applied either fix). And while down for maintenance as well!