I suspect this issue is directly related to using CCK 3.x.
On clicking add another item, all node relationships buttons disappear. It may or may not be related, but using the nodrelationships multiple search and reference widget results in multiple nodereference fields upon save, but they are all empty (the references are not actually entered). Single references seem to work fine.
I think these issues are both related to changes introduced into the 3.x branch of CCK for handling multiple fields.