Make sure you have specified the correct SMTP server in the power store admin section. If you are not sure of the correct SMTP server to use, contact the host, they will be able to help you.
If you are still having difficulties, who is your hosting provider?