You can enable tethering by following the UltraCfg install instructions on this post.
Make sure you reboot after you copy the apk, then launch UltraCfg enable tethering ON.
It may seems to freeze, just wait..
After the app sets the setting start tether you will see the blue icon in notification bar, and bam you have tether back
Just press the home verify if it still shows verifying, after your see the blue icon.