Hi all, it had been a while since I updated my firmware (~6 months to a year and I can't remember exactly what version I was on before), I was set to long-term and updated to 6.48.4. A couple days later my android phone and tablet stopped being able to find my Nvidia Shield TV using the Android TV Remote app. Guessing the cached info expired and it had to research for the TV.
I went through a bunch of other troubleshooting to see if I could fix it issue, updated to 6.48.5 and then 6.49, but finally downgraded a bunch of my routers and switches from the CAP's back to the CCR router and CRS125 connected to the Shield to version 6.47.9 rebooted my Shield TV and the App was able to find it again and connect.
Hopefully this may help someone else, there seems to be something in the newer releases blocking whatever the Android remote services uses to advertise/locate the devices.