Paypal Recurring Transactions Are Broken in 4.7
You don't say which version of CiviCRM you're using. There were some fixes related to PayPal in 4.7.13, in particular look at CRM-18483 If you're not up on at least 4.7.13, it would be worth upgrading.

(Edited to correct a typo)