are you using Paypal Payments Standard as the Payment Gateway?
In the case of CheopisIV, the issue was caused by using the wrrong address for the IPN file in the paypal account.
Go to your power store admin section. In the payment gateway settings copy the address for the IPN Page. in your paypal account, you will need to set the Paypal IPN System to use this page.