Are your debug logs including one that talks about DoExpressCheckoutPayment? If so, what's its "result" response? Any errors mentioned there?

If the problem is that PayPal is failing to do something with the submitted transaction, it might be necessary to get *them* to look at it from their end: www.paypal.com/mts