Welp, looks like it's not actually IP related. You need a US credit card with a US billing address to buy apps; you can fake the number (all 0's works, see the other answers) and address to download free apps. Then ensure 1-click ordering is turned on in your Amazon.com account (the Appstore will prompt you to do this and provide a link). A prepaid credit card in USD might be a good way to do this for people outside the US, I'm not sure.
Update: Some users seem to be reporting that Amazon is now blocking non-US IP addresses. This isn't 100% accurate, since I access the app every day from Canada with no issues. It may block specific countries though, in which case you'll need a US-based proxy/VPN. Make sure you trust it, so that your account credentials aren't compromised; don't use Tor / Orbot!
Update: You have to now prove to be a US resident by accessing the store with a US based IP once. It's sufficent to use a US proxy once.