When you start the PC (as in from being turned off) you have no Internet, but restarting allows it to turn on....
Do you have Windows 7 set to automatically log in? If so, disable that - and see if waiting about 10 seconds before entering your password allows it to work....