I have a Galaxy S3 T mobile 4.1.1 and had the same problem. I downloaded Titanium backup and uninstalled Tethering manager or tethering Provisions depending on your provider and installed 1-click tether and tethering worked for me. Don't forget to backup the app before uninstalling it.