We found exactly the same problem with EE 2.5.5, Expresso Store 1.6.5 and PayPal Express with a client website. I believe something changed at PayPal which has affected the ability of Expresso Store to communicate with PayPal in the way that it always has. We were warned about the IPN changes but this should not affect the workings on Store.
You may find it useful to know that for us it only seemed to affect 'Guest Checkout' transactions. I.e. transactions where a customer wanted to pay with a credit/debit card at PayPal. Its unlikely you will replicate the issue if you simply log in to a registered PayPal account and try to pay. These transactions seemed to be going through without a problem.
There appear to have been changes on the PayPal Express Checkout page that makes it harder for the user to pay with a credit/debit card. At the point where the customer opts to pay with a card, fills in their card details and then has to agree to Guest Checkout terms that transactions would not proceed forward.
Our solution was to integrate Stripe for card processing. I had already started the developing the checkout process for inclusion of Stripe as my client wasn't happy about how PayPal was pushing their customers to register. When the problem you describe was spotted we decided to complete the Stripe integration as this was going to be quicker to implement than troubleshooting further the PayPal changes.
Following successful Stripe integration we switched off PayPal Guest Checkout with PayPal now being 'Account Required'.
The checkout review details page now has Stripe card payment as default with an option for the customer to switch to PayPal.
I should say there is an annoying bug in Expresso Store 1.6.5 that may cause you problems if you decide on a similar solution for your client. It affects the use of radio buttons for selecting payment gateways: https://expressionengine.stackexchange.com/a/15106/1019
Once I identified this I implemented gateway selection using a select dropdown instead.
If you find a fix for the PayPal card processing instead please do post back here. I do intend to investigate this further but with Stripe working the pressure is off.
Good luck,
Steve