It sounds like the files each user creates are owned by the creator. That is normal. But then only the creator can modify them.
To make this work, both need to be members of the same Group, and each must have Group Read/Write permissions on the files/Directories created.
You could also be running afoul of this obscure problem:
You can create a Group directly in 10.7 in
System preferences > Users and Groups ...
... and add the 10.7 user to the group you create.
For a Mac running 10.5, you would have to do something completely non-intuitive -- download Server Admin Tools for 10.5, and run WorkGroup Manager to add that user to the group.
Then on your NAS, you would have to set Group permissions so that members of the group you created have Read/Write access to the files you wnat to share.