Yep - I installed all the patches as listed & it still doesn't work. Paypal Express Checkout does not work at all - when that option is chosen, it sends you to a page that says "The transaction is invalid."
When Paypal IPN is chosen, it takes the customer all the way through the transaction in Paypal - sending & receiving the money - but when they're redirected to the store, there's no order. I have no record of the order in my admin & they cannot download their order.