We are having a similar issue at my work, i have applied a fix (Untested as of yet, only about 7 staff members are here during the holidays)
It seems to be a random issue that some of our laptop users experience.
If your using group policy to push out printers, use the FQDN of the print server
http://i.imgur.com/8g4czhR.png