Name Resolution not working

Seemed like a simple problem. Took over a 9 station W98 peer network and need to get this working ASAP.

New NAS device only accepts TCP/IP. 4 machines can ping other stations by IP address, but not by name, therefore they cannot connect to the network shared drive.

Here’s what I’ve done.
1) Re-installed NIC drivers.
2) Replaced NIC cards.
3) Re-installed W98 on workstations.
4) Upgraded IE to 5.5
5) Blew out IP stack and network and re-installed.

Does anyone have any other thoughts?