I'm assuming this is on your home network. Do you possibly have a whitelist set up for the router/modem and you need to add the new MAC address for the new Kindle? I have a whitelist for my setup and since I so rarely add new devices, totally forgot about it once and spent hours trying to connect a Kobo to it (and failing miserably until I checked more settings and remembered the whitelist). Definitely one of those
days for me.