I just received an answer from PayPal about what they believe the problem might be:
It seems that i have found the solution. The Express checkout process is not complete. In order to complete the express checkout process you would need to pass parameters for SetExpressCheckout and DoExpressCheckout. From our end, we see that only SetExpressCheckout is being called and there is no DoExpressCheckout. If you are developing using Paypal Classic APIs these parameters will need to pass. However if you are integrating using eCart and they are handling all the necessary codes to pass, you would need to contact them and inform them that the codes they are passing is incomplete.
If you need further instruction regarding the problem you are facing, do contact us.
Merchant Technical Support
PayPal, an eBay Company