When I attempt to turn Internet sharing on, I get an error message:
Connection not shared
There's no cellular data connection to
share right now. Check your cellular
settings and signal, and try again.
My phone's data connection is enabled, I have five 'bars' of reception, and they're joined by an 'H', reflecting my active data connection, and I am able to use Internet Explorer and other things that require an Internet connection. My provider, Mobilicity, does not restrict tethering.
Lumia 710 has got the internet sharing with the latest software update. So, please make sure to check if your phone has the latest update. For more details about updating the software, please check this link.
You may also check the following:
Hope this will work.