Unable to connect to samba shares on a NAS

My home network consists of three machines, one is WinXP, the other Win2000 and the one with the problem is a dual-boot PC: WinXP and Ubuntu 7.04. They are all attached to an ADSL modem with a router Thomson SpeedTouch 510. The router also runs DNS and DHCP servers. Recently I added a NAS box to the network, RaidSonic NAS IB-2000, which is actually running a small linux distro including a samba server. I set up a samba share for myself on the NAS and another for my son. I can easily access the appropriate shares from all Windows machines, including the dual-boot one, however I am unable to access the same shares from the same PC running Ubuntu 7.04, the system behaves completely erratically.
I have searched the net for instructions on how to mount the share and they all seem to suggest the same commands as the NAS manual: smbmount //servername/sharename /mountdirectory -o username=samba_share_username,password=samba_share_password,dmask=777,fmask=777

So I created the mount directory, opened the terminal and sudo'ed the above command. All I get is an error like this:

6978: session setup failed: ERRDOS - ERRnoaccess (Access denied.)
SMB connection failed

I then tried typing smb://servername/sharename in Nautilus and it asked for credentials and displayed the share, but when I tried to copy something into it, I got a time-out error and the file was not copied correctly.

I tried to have a look at the network using smbtree. Once I achieved to get this information:

MUZIK-HOME
        \\MARTIN-PC
cli_rpc_pipe_open: cli_nt_create failed on pipe \srvsvc to machine MARTIN-PC. Error was NT_STATUS_ACCESS_DENIED
        \\ICYBOX ICY BOX NAS
                \\ICYBOX\lp Generic dot-matrix printer entry
                \\ICYBOX\ADMIN$ IPC Service (ICY BOX NAS)
                \\ICYBOX\IPC$ IPC Service (ICY BOX NAS)
                \\ICYBOX\zdenek.muzik
                \\ICYBOX\zdenek-share
                \\ICYBOX\public Folder Share for public
                \\ICYBOX\martin-share
                \\ICYBOX\common-share
                \\ICYBOX\admin

but in all other cases of trying this command there is no reaction in the terminal at all and it goes back to prompt after cca 2sec.
I searched the forums and various Linux portals, but I am always getting the same instructions which do not work.

Do you have a suggestion what I should try next?
PS I started trying this on Ubuntu 6.10 and the problems were exactly the same.