In fact, the documentation about readdir mentions the fact that you need to prepend the directory again.
Just in the (very unlikely) case that the files actually exist, the error message suggests that the OP is trying to move them across mount points. This would happen for example if you have two disks mounted below /mount:
/mount/hda/dir1
/mount/hdb/dir2
Then, moving files from /mount/hda/dir1 to /mount/hdb/dir2 would mean actually copying the bytes between the two devices. At least the mv program (and thus, maybe also the rename() syscall?) on my Debian system does such copying nowadays...