One of the possible solution which I go through
One of community member also faced the same issue in Magento version 1.9. If you change your password in paypal after setting up Magento and it has special characters, Magento fails to update it in payment method configuration. Removing special characters "fixed" the problem.
I hope this will help