I have a Galaxy S3 (SGH-I747; Android 4.1.1; AT&T) and a Galaxy Note (SGH-I717; Android 4.1.2; AT&T). They are both on the same AT&T family plan, which includes the tethering/wi-fi hot-spot (i.e. no need to root the phone).
The wi-fi hot-spot works with both phones to connect my laptop (Ubuntu 12.10; Asus A53E). But I can only use the USB tethering with the Galaxy Note. Any problems with the GS3 I don't know of?
I've solved the problem using :
https://play.google.com/store/apps/details?id=com.tetherunlocker
Open the app, click on "unlock tethering", wait for the video completion, and magically tether works, try it and le me know.