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