No tengo limitado nada de ips ni nada y en todo el resto de dispositivos va perfectamente (iMac, iPhone, Pc, PS3, otros móviles...)
No sé si aquí te refieres al bloqueo por MAC, pero míralo por si acaso.
Lo único que se me ocurre es que desconectes todos los cacharros de la red, elimines la configuración de WiFi del Kindle, reinicies (NO resetees) el router y pruebes a volver a conectar desde el Kindle.