Think I got it. The following works for me - pinging by NetBIOS name from Fedora to Windows and vice versa.
Samba config on the Fedora box:
WORKGROUP = WORKGROUP
NETBIOS NAME = FEDORA
(yup, that's about all that's really necessary there for just allowing the Fedora box to use NetBIOS.)
hosts: files wins dns
Make sure smb and nmb are started:
service smb start
service nmb start
And to load them on boot:
chkconfig smb on
chkconfig nmb on
Now if I do "ping fedora" (and also I should mention that NetBIOS isn't case sensitive) from the Windows box, it resolves it just fine.