Phone not connecting locally

Hi all.

I have HA setup on a VM on Linux. It is connected to the wifi, on the same network as the phone. I also have another phone, and an ipad that are connected to the same wifi. Both those devices connect to HA fine. But, my personal phone, does not locally. It ONLY connects via Nabu Casa’s link.

I can open my ipad, click on HA, and voila, connected to HA. I can have my phone right next to that, connected (confirmed many times) to the same network, and it will simply say "Unable to connect - refresh internatl/external URL.

If I then DISABL wifi on that phone, so that it goes through the celular data, connecting to Nabu Casa’s link - it connects, and all works 100%

Have checked settings on phone:
Internal connection URL = http://homeassistant.local:8123/
External connection URL = My Nabu Casa link

Above is identical on ALL my devices (the three mobile, as well as my two laptops and PC.)

The phone is a Samsung S23 Ultra, on latest Android.

Any thoughts?