To OP:
Is your phone on the home wifi network, and NOT the cell network during setup? Your Dot and phone must be on the same (SSID) home network, (except when first setting it up when the phone must be set to the amazon-XXX wifi signal until you are told to switch to your home network.
Also, the following statement made above is totally NOT true: (If you have a dual band router, make sure that your Dot and your phone are on the same band,... )
They just need to be on the same network (SSID) but do not need to be on the same band.
Since setting up my Echo. two Dots and two Taps, the Alexa devices have always been on my 2.4G band, and my phones and tablets are all on the 5G band. My wireless devices that I want to run faster for video streaming, file transfers, etc are all on the 5G band, and all other (slower) devices (like audio-only devices such as Alexa devices) are still on the 2.4G band. All work perfectly fine. Basically, reserve the 5G band for devices that MUST use the fastest band for best results.