you may need to enable wins support in the smb.conf
I am assuming you can still map to shares on the linux box? with the ipchains?
If you can then it is just a matter of the linux box broadcasting names via wins, also you may need to set up Lmhosts on your xp!
I was able to see my xp box when using samba as a wins server.
now I have samba as my primary domain controller and it shows it no problem (although samba is still using wins support)
hope that helps.