After looking in the forums and exchanging message via Twitter with Stadia support I stumbled on what my specific problem was.
Like many people I was trying to add another Chrome Cast Ultra "CCU" to my Stadia app but when I would try the App would just say there wasnt any Chromecast nearby.
What I stumbled on is I have an Actiontec Single Dual-Band Wireless Extender (WCB3000N)
I broadcast the same SSID, and its the same "network" technically but Im pretty sure Chromecast has some form of issue in general. Often I'd notice that I would try and cast something but the Chromecast wont show up.
When I moved my phone and controller to nearest access point (main one) I was able to see the Chromecast listed and get it added.
Im not sure if this is a specific issue with this older ActionTech Extended, or extender / mesh network setups but given the number of posts I found hopefully if you are running a similar setup this helps.
One thing that lead me to think it was the wireless SSID broadcasting was that the Stadia controller was able to unlock the CCU I was trying to add. So thats a sign that from a network stand point it could talk to it. Id just get stuck on the screen that I needed to add it via the APP.
Here is a good post I found about Chromecast and mesh networks ( even Goggle Wifi)
Ive certainly have seen issues with some older devices in my setup, especially older Belkin/Wemo stuff I used to use.