Japanese UPS/USPS equivalents can handle addresses written either in English, Japanese or romaji transliteration. They can even deliver poorly transliterated packages to the right address. Just make sure you enter the correct postal code so amazon uk sends your package to the right local deliver boys in Japan.
When I buy stuff from Amazon US and send it to a Japanese address, I always write in romaji in the US way, e.g.,
105-8511 東京都港区芝公園1丁目5番25号 would be
1-5-25 Shiba Koen, Minatoku, Tokyo 105-8511, Japan.
When I was in Japan, I used to receive letters and packages with really messed up addresses. And there were no problems.
Edit: Oh, those random letters you got on Amazon UK doesn't bode well. Most likely you should enter the address in romaji.