I found the strangest coincidence possibly but I think it potentially solved this whole issue. Here is what happened.
Re-downloaded and deleted all images/installers I had been using for both Android and UT
After re-flashing the stock 13 Image I was having the exact same issues on Android now. Flashed stock 15 for science and confirmed this was also happening there.
After rolling back 13 and playing in settings it turns out that Enabling "Allowing 4G Calls" in Android 13 settings resolved my data issues in Android.
Flashed 24.04 Daily (r561) and found that not only did data work and it gets 5G now, MMS also works (with WIFI off) before it constantly said there was a network issue.
I am not sure if this is the fix coming in beta 2, but its miles better than my experience yesterday!