I'm just a somewhat-educated bystander, but based on my understanding of Android and Nexus, there is no way for Straight Talk to directly alter any of the software on your device, with some rather large and indistinct gotchas.
They certainly do not have any custom apps running to detect and block tethering activation.
What they may have are APN-based restrictions, and these are probably accidental. When a cell phone signs on with a network, and starts sending and receiving data, the carrier sends a bunch of configuration information, including APNs (named endpoints where cell phone data turns into internet traffic). Given that this phone is originally from T-Mo, and T-Mo uses dual APNs in their stock config (one for phone traffic, another for tethered devices), this may be part of things. In the ideal world, flashing stock images should have updated the radio with an unlocked version, and should have reset APNs to carrier default, but if this wasn't done, it'll still be trying T-Mo's default APNs (Straight Talk is an MVNO, or reseller, for both T-Mo and AT&T, and for a phone that was previously T-Mo, they will leave it on T-Mo only). If you're on T-Mo's network, using T-Mo's APNs, but you're on an MVNO that just plain NEVER resells tethering, it's entirely possible that your phone is trying to handshake with the tether APN and is failing. That usually takes a few seconds, but it fits the symptoms you're describing. It usually produces more useful error messages, though.
<<<For OP's use ONLY, NOT RECOMMENDED, VERY RISKY PROCEDURE:>>>
You can try this trick, which unlocks, modifies, then re-locks the APNs, this sends both phone traffic and tethered devices over the usual T-Mo phone data APN. IF YOU ARE CAUGHT ABUSING THIS, T-MOBILE WILL SEND YOU A NASTYGRAM AND BE DIFFICULT. THEY MAY EVEN END YOUR SERVICE AND REFUSE TO SERVICE YOU. Sorry for the all-caps, but this is Very Important.http://forum.xda-developers.com/showthr ... ?t=1962752
<<<Again, DANGER, READ COMPLETELY, NOT RECOMMENDED.>>>
But yeah, Google don't care, ST isn't tampering with the on-phone software, they're most likely just innocently getting jammed up by T-Mo baseband/firmware/low level network info. Since you're basically trying to get a service that isn't advertised or sold to you, you're on your own, but you can try. Good luck.
Sources for above, in case anyone wants my bone fides: Owner of a Samsung SGH-T989 (Gal SII T-Mo edition) that has completely forgotten it's past life and doesn't really know what it is anymore, running a self-compiled build of AOSP, with Nexus bits Franken-built back on, with a mildly custom/haxx0red firmware/radio (Such hax, so confusion, many spoof! Wow!). I like to call it my Google Nexus SII. I'm no longer doing such low level hackery on my phone anymore, but I travelled pretty far down this rabbit hole.