I was in an almost identical situation when I applied for this card 2 weeks ago. The only difference is that I have had credit cards but my history is still pretty short. However, I had a little problem on my credit report so it equals out.
I was also instantly declined. I called up and after exasperating the first agent, she transfered me to a supervisor. I told the truth that I spend a lot of money yearly and would like to move it to SPG Amex for the points and for the positive customer service experiences that I have heard from others. I told him some more personal stuff and basically convinced him that it would be beneficial for Amex to give me a card. After a little while longer, he acquiesced and told me that he can put it in for a manual human review. He said that the Amex website credit check is fully automated and that there is something called an Amex risk factor (or something like that) which is comprised of many components and if you do not pass, it will decline you.
This was on Thursday. He told me to call on Monday and see how its coming along. When I called, I asked to speak to a supervisor right away. I reiterated my points and asked her to check. I had to convince her also that I should get a card. She actually called the underwriter while I was on the phone and then spoke to someone else all while I was on hold.
After she was done she got back on the phone and told me my card would be in the mail the next day. They actually overnighted it and I got it on Wednesday.
My point is that unless they notated things on your account to not give you a card from your previous calls, you should be able to ask them to manually review it. Call back soon thereafter and make your case. I think this is your best chance to get the card now.
Otherwise you can follow the advice above and build your credit, and then reapply further down the road.
Good luck.