Turns out that Paypal Express and Magento were not playing very nice. Paypal would accept all the info Magento had to offer when doing a Paypal Express payment type.
But it was Magento preventing the sale to go through. On the paypal/express/review/ page there were no shipping options to select causing the “Place Order” button not to finalize the transaction.
So after hours of irritation and experimenting we finally figured it out thanks to this post.
It wasn’t Magento at all. It was the extension that was installed on our clients system. We modified the code to accept version 1.6 and low and behold like a magical wisp of a wand the sale went through in such a happy traa la la la kinda way!
So if you have the Admin Custom Shipping Rate module by i960 and you are experiencing some spats between Magento and Paypal Express trying changing the code to accept your version of Magento. Oh, i960′s extension is a great one by the way We have had no issues with it until now.