I've edited this severely because the problem was solved by my service provider. But someone else might have the same experience and might be looking for this solution.
After Samsung pushed the Android 13 upgrade to my Galaxy S21 5G, I found that I could connect my laptop to the mobile hotspot feature of the phone. But the laptop could never "reach" the Internet over cellular data.
It could, however, "reach" the internet if the phone was connected to local WiFi.
I jumped to the conclusion that the update was to blame. Turns out, it was not.
Support tech at my service provider "reset" my hotspot from their end. Problem solved.
Solved! Go to Solution.