I spoke to Paypal - and was pleasantly surprised to get through to a merchant technical support department. We discussed the issue, and simulated a transaction, and found a Magento -> Paypal API bug that was causing the problem. Paypal provided an email reply, that i have quoted below for reference.
Now I could try to hack magento to fix this, but that will not fix the problem for other users, so I thought I would highlight this issue here in the hope that the paypal development team would look into this.
Thank you for contacting PayPal Merchant Technical Support. It'be been a pleasure to talk to you over the phone.
As we have discussed over the phone, it looks like Magento is not passing the Start date with the correct time format in the API request sent to us. Below is the API request received from your end :
Apr 22, 2016 07:10:38 (1461280238)
"BlueOnyx Professional Edition (BOPE)"
As you can see, the profilestartdate is not sent with the correct time format as " 2016-10-21T04:12:25Z" . In this case, kindly refer to Magento and check with them on how to ensure the correct time format is passed in the API request.
I hope I was able to address your inquiry to your satisfaction, should you have further questions relating to this inquiry or any other issue, please do not hesitate to let me know.
Sincerely, Naginitra Merchant Technical Support PayPal, Professional Services