O problema foi causado porque nosso firewall foi de alguma forma configurado para atuar como servidor DHCP, além do servidor DHCP regular que tínhamos. Como resultado, os computadores que receberam o endereço IP do servidor DHCP normal funcionaram bem. Aqueles que receberam seu endereço IP do firewall não funcionaram!