when UPS first creates the account, it wont have permisions to acess the production lookup serverr, you need to contact UPS Support to have the account updated to enable access to the production server.
if you continue having problems, enable debug mode in the Power Store admin, this will cause the session contents to be written to the failure page, this will contain details about why the transaction is failing,