win7 Can print only after a restart

[flynempire]

I have come across a problem with a client computer. It is one of those Lenovo All-In-One PC's where everything is in the monitor.

If a cold boot is performed the computer logs in to Windows but the printer is gone when in reality it is installed. Once a restart is performed then it appears and everything is normal for the rest of the day,
 

What gives?

I should mention 2 things. The printer is not local but a network printer and I am noticing that the connection icon in the tray shows the yellow exclamation showing an error but the machine is connected to network and internet as I tested it myself.

I am hoping someone can shed some light on this as it is very strange. First time I come across this.
 

Thanks,

Victor

I should also mention that Windows 7 Home Premium is installed and the rest of the machines on the network contain Windows 7 Pro. The Lenovo is model 77452SU