Amazon is like the Harvey Two-Face -- half amazing and half frustrating. I have a Kindle Fire in Australia, but as Australia isn't an official country yet, Amazon Market doesn't work. And by doesn't work I mean I can't even download free applications without an American credit card. Amazon support know this and just apologise.
When friends ask me about the Kindle Fire in Australia, I won't say good stuff about it. When it finally is released here, do you think they'll be it? No. They'll remember I said it was annoying for some reason. The reason doesn't matter. Bad is bad so they'll decide, many moons ago, that they're not getting it.
Amazon in Australia are horrible. For many, many reasons[1].
[1]: Amazon Affiliate program pays out by gift certificate or check to Australia -- http://www.problogger.net/archives/2008/11/29/an-open-letter...
I changed the address to a US one, and the purchase went through. One of the positives of living in a border city with multiple shipping addresses, I guess.