I have the same issue however I always thought it was related to my Chromecast been connected directly to the ethernet and not the wifi.
Is are you connected using a ethernet wire to your Chromecast?
Hi @metalshark , sorry you're one of us...
After the nth time (probably 20th), I managed to get a controller to connect. Not the other though. I opened a support case.
I suggest contacting Stadia Support, their chat is open 24/7. Good luck and keep us posted!
It seems that the problem was related to my Moto X Force smartphone, which was not able to connect the controller to my Wi-Fi. I have now tested it with a Pixel 3a XL and it did work on the first try.
I have a similar problem with connecting the controller through my Pixel 4XL.
Worth noting that it's a controller I had previously connected to the same wifi without any problem in the past. Today after lending the stadia to a friend and changing my phone to the Pixel 4 XL, it's become totally impossible to connect it again...