You might be able to pre-order with Origin still. Go to profile.ea.com and check your addresses listed there. If they don't match the billing address you're using in Origin, you will get the payment authorisation failure message.
You can change your addresses at profile.ea.com whenever you want, so if you need to change the address back, you can. I think you should keep it, however, until your card is actually billed when the game is released. Hope it works for you.
Just an edit to say, I had this problem when trying to order Sims Medieval. It kept telling me it couldn't authorize the card, but my addresses at profile.ea.com didn't match. I changed them and it worked.