Things I've tried:
Additional information: I changed routers a while back and just now got around to reconnecting the device. It was working before on the old router. Nothing seems to get it to connect to the new one. No other problems with connecting other devices in my house.
This is not the experience we want you to have and thank you for doing all the steps, let me help you. A few questions: which Nest speakers are we working with? When you did the factory reset, was it the same steps as what you see in this link? What’s the name of your new ISP and router/modem?
To eliminate network issues, please try setting up your device using a mobile hotspot. Please note that you will need two mobile devices for this setup (one will serve as a router and the other to be used to set up your Google Home/Nest devices). Once done, check if your device will have the same behavior.
Let me know how it goes.