Is your power store a clean install of 4.01 or was it an upgrade for 4.0 to 4.01?
when you get to the failure page, look at the address in the address bar, does it include:
as a query string variable at the end?
at what point to do you get sent to failure page?
After clicking the express checkout button on the cart page?
Or after clicking the submit order button on the pp_confirm page?