I had a similar issue and found an advanced setting in Windows under the network setting that said Enable FIPS. I did that and it started working.
Seems to be a Mac thing - after the recent updates I hoped it got fixed but the issue is still present. I can't use internet sharing at all with my MBP. It connects, works for a minute, then disconnects. Then it just keeps on disconnecting every couple of minutes.
I don't need a tethering plan here - and tethering works well with the iPhone 5.
I'm connected right now via my iPad 2. I did have to reset my network settings though.