I have mentioned in the past that we go to Menorca a reasonable number of times - and I bought a YOIGO sim, which gives me 1gb of reasonably fast internet access for €10 per month.
I am in the fortunate position of having a Windows 'developer' phone, so I pop the Sim in there, and turn on Internet Sharing.
So, as usual, I plugged everything in, and my wife's phone connected immediately, as did the Surface RT. I configured my phone to access the 'access point' and started getting my mail. The only problem was that although my laptop connected, I couldn't get internet access, or get access to my Office365 mail server. Strangely enough though, I did see people popping up on-line on Skype.
I had my Zoom Modem with me, so I put the YOIGO sim in a dongle, plugged it in, and away we went - for 5 minutes. I got a good connection, and then it dropped after about 5 minutes. Remove the dongle, put it back in, works for 5 minutes and then dropped again.
I couldn't really complainto YOIGO about this, as I was using an unlocked T-Mobile dongle, which possibly wasn't compatible. So for the next couple of days, I alternated between the Zoom modem, the Windows Phone, and an assortment of bad language.
I finally got brassed off to do something about it and searched for a solution (not on my laptop though as it wouldn't connect). I find it frustrating searching on one machine to fix a problem on another - but that may just be me.
I hit paydirt pretty quickly - saw an article called Internet sharing is not working on Nokia Lumia 925 solved which looked interesing. It talked about DNS entries. I had already compared the settings of the Surface RT with the laptop and they looked the same, but operated differently.
The article suggested pinging 126.96.36.199 and then www.google.com - the IP address worked but the name didn't, which points at a DNS problem. The article suggests using Google Public DNS and much as I don't completely trust Google, I went for it - and it WORKED. Suddenly mail came flooding in, and I could access the Internet.
I had used this laptop and Internet sharing in the past - so I can only guess that the update to Windows 8.1 mad a difference.
Anyway, if you are having problems this may just save the day.