I have not upgraded to WP8.1 yet as Tethering is the only data connection for our home and the WP8.0 is working perfectly. I actually bought a Lumia 520 as my Android (Moto X) was doing exactly what you people are describing with WP8.1-Tethering. At a guess, it appears to me to be a QoS thing as internal stuff is taking precedence over Tethering.
Well, that's what I am pretty sure was happening with Android as it would often suddenly announce "6-new updates installed," even though I have App-updates off. If it had to update internal Apps, they were getting first byte
at the data path and dropping the Tether.
Seems like WP8.1 developers may have fallen into the same trap. That Tethering issue was at the head of the fix-it-list for Android 4.4.3 update just rolling out now. If WP8.1 doesn't lift it's game on this Tethering issue, I may have to reluctantly go with Android 4.4.3.
That's a bummer as I really want to go with the WP8.1 update but cannot take the risk of faulty Tethering. I am watching this thread closely!