Sounds like DHCP may not be getting an address.
You can verify this by
ipconfig /all - in a command window.
In the section for the relevant interface the address will begin "169.254." Unless autoconfiguration has been disabled in the registry in which case it might be blank. autoconfiguration is on by default.
If this is the problem then the following is relevant.
Beginning with Vista, MS screwed around with (screwed up) DHCP.
I can't really tell you what to do exactly or why removing the network helps.
I have been a data network engineer for nearly 20 years and I can't get my own stuff to always work properly in this respect. I guess they want people to just use Linux.
The works once aspect may be connected with windows remembering the last dhcp broadcast flag that worked.
See if this helps.
DHCP Broadcast flag handling in Windows 7 - Microsoft Windows DHCP Team Blog - Site Home - TechNet Blogs dhcpblog at microsoft
It looks as if they will assist end users but you will have to be prepared to enable logging, repeat the problem and send them the logs.
Usual caveats about registry editing apply. Don't, if you don't now how to take care not to mess it all up.
###
With my Android smartphone as hotspot I am reduced to waiting 2 minutes for DHCP to work (sometimes - yes it varies). Smartphone is not rooted and I cannot change any dhcp server parameters on the phone.
## You could try waiting for two minutes letting it retry automatically, well make it three to be sure.
With a public hotspot that I sometimes use it usually works but sometimes the hotspot responds with the wrong reply type (broadcast vs unicast) and I cannot get an address.
Finally this is the process that I use to remove errant wireless hotspots from windows and to start again.
command window
netsh wlan delete profile name="BT-123" -- Use your hotspot name (SSID) in place of BT-123. Names are case sensitive and some have spaces. Double quotes are essential.