You will have to reset your phone to factory settings and DO NOT run any network tool (e.g. Nokia Network Setup) afterwards.
The network tools somehow screw up the internet sharing. Also, if you have LTE in your area, it most likely will generate the same error.
Type ##3282# go to settings (lower right) and switch to 3G. Even if it is set to 3G, make sure you scroll to it once more. Plus, make sure you are on the latest firmware.