WINS not doing its job

[Brian Henning]

Hi All,
   Just got in some new Dell Dimension 3000s preloaded with Windows XP 
Pro.  And for some reason, they're failing to correctly use WINS (i.e. I 
can't reach other workstations by their netBIOS names, only by IP..).. 
At this point, we're just a lowly workgroup (too many XP Home machines 
that would kink up a proper AD domain), and this problem hasn't shown 
itself before..  So I'm at a loss as to where to start poking to fix it.

Suggestions?

Much thanks,
~Brian