Is your application split such that each user has an mdb file on their local computer linking to tables in a shared mdb file on the NAS?
Have you repaired/compacted the mdb file on the NAS?
Is anyone accessing the NAS using a wireless/wifi connection?
Do all users have the latest updates for Access/Office 2003? I think the last service pack for Office 2003 was SP3 but it may be hard to find these days.
-Bruce