Tried SMBFS 1.66 on the A4000, has trouble connecting to both my NAS, and a Samba server on my Laptop. smbclient from the Samba 2.2.5 archive on Aminet works fine on the other hand, can browse, create, delete, etc.
My guess is there is something up with SMBFS. Debugging it sounds like a good idea. Also, send an email to the author with the issue, he might be able to help.
Other than that, updating the firmware on the NAS is the only other thing I can suggest.