Do you know why they are having problems? Is it because they are not signed up as a Paypal member? If so, are you in a country in which you can set up your Paypal account so others do not need to be members?
Or do you direct users over to Paypal's secure website and the problem arises when the user is re-directed back to your website? If so, are you in a country where you might be able to handle the transaction on your secure website?