А после перезагрузки компа пробовал его пинговать? Может сетевая карта инициализируется долго. И соответственно задание на печать не доходит до него.
Как вариант просто принтер подключить в сеть и уже оба компа подключить к нему по сети. Такая конфигурация будет гораздо удобней со стороны администрирования.