Application Error AndroidWebKit classes are missing. Please copy android_interface.jar from AmazonWebView SDK to app's libs folder and the rebuild the app.
Para solucionarlo hay que bajar el Amazon WebView SDK desde https://developer.amazon.com/sdk/fire/IntegratingAWV.html, luego descomprimirlo y copiar el archivo awv_android_factory.jar al directorio "app-directory"/platforms/amazon-fireos/libs/
Despues abrimos Eclipse, volvemos a exportar y el nuevo archivo apk generado lo subimos al test de Amazon Appstore y veremos que esta vez no da ningun error.