It looks like it would work to me, so I think you have to debug. I'd start by dumping the session on a page you can look at. Add a new blank page to your site and put this on the page:
Then after you get to the checkout failure, go to that page and view the source code. It should have a lot more information that would allow you or me to figure out why it is failing going to paypal.
If you can't find it by looking at that page (view source to see it), then tell me the location of the new page and I'll take a look.