It is windows 7 (if you have it) that needs that time to identify the network and label it (home, public etc.). During this period there is no internet connection because the ip address obtained via DHCP is not yet assigned to the network card. The message during this process is "limited connectivity". In this specific case it is only a delay and not a malfunction per say.
Yes it should be only 1st time as long as you don't change in the future encryption type, SSID name or wireless key in the hotspot settings.
Does it normally take a few mins to get past "Limited connectivity" or was only the first time you used app?