what Payment gateway option are you using?
This may happen with PayPal Payments Standard if you do not update the paypal account to enable IPN and enter the IPN page address that is found in the Payment gateway section of the Power Store Admin panel.