I suggest you read up on samba and see how to get it on the same domain.

Also have a look at how DNS names are being resolved on the print server.

Windows boxes happily use their own dynamic naming system.