Very interesting ThirdOfSix, I had similiar issues on my home network with windows and linux boxes. This may explain why.
My work around was to replace all mentions of machine names with ip numbers, then bookmarked them in konq, smb4k, and printer configurations. It has worked pretty good since then.
Hope this helps.
Desktop: AMD 3.6ghz X4, Gigabyte MB, 8GB ram, Multiple PCLOS's, 22.214.171.124-pclos3.pae.bfs
Server: Intel 3.4ghz X2, 4GB RAM, SATA, gnome2, *.pae.bfs, Headless, Servers: LAMP, FTP, Samba, Print, PXE, BT
HTPC: Phenom II X4 2.8ghz, 4GB Ram, 1TB SATA, PCLinuxOS-KDE, NVIDIA N220GT HDMI, *.pae.bfs