Sounds like the first denial was due to an automated fraud check with a false positive. When that happens, it's a good idea to call your credit card company right away - if it was such a fraud check, they can usually reactivate it right away and whitelist the merchant you tried to buy from, allowing you to retry the transaction - and more importantly, ensuring that your card isn't suspended and later declined again at an inopportune time.