I had the same issue for a very long time and i just figured it out.
heres what i did:
go into your search and press the 'eye' button so you can scan a QR code
go to the link and scan the access point code
Nokia Windows Phone 8 App Updates - Nokia Support Discussions
install it and once its done, at the bottom of your settings list there will be 'Access point'
go into and and you should see your carriers APN settings etc and if not add them
now try to turn on internet sharing, it should work now with no issues whatsoever
Good Luck!