Let's be clear: to buy Apps or Books, you need a US Address & Credit Card. It doesn't matter where in the world you are physically located, you can buy eBooks or Apps just fine. However, that does NOT WORK for videos. For videos you need to be connected via a US IP address. I can confirm that VPN solutions work. (For the Fire, there are currently no VPN solutions in the App Store, so you need to either set up a DD-WRT router, or side-load one of the unsupported VPN solutions from the Android Marketplace.)
I was able to watch a free Amazon Prime video with acceptable speed over a VPN connection using the service at
http://www.hidemyass.com. With the VPN disabled, I had been blocked by Amazon because my local IP address was recognized as in Canada.