How to diagnose a tethering issue after swapping sim cards?
The issue is one of Access Points, just not one configured in the tethering settings.

The fix was to go to Settings, then More under Wireless &amp; Networks, then Mobile networks then Access point names. Finally, edit the APN that the network configuration sent. In there, I found that the APN type was just default

It turns out that default is enough for the phone to get online, but not for tethering to work. So, I changed it to default,net,dun, as shown:



With that in place, Tethering magically started working

So, the fix was APN related, just that it isn't something (in Android 5.1 at least) that is setup in the tethering area, it's in the mobile networks area and needs the dun and net settings