Something wrong with the volume's CNID DB using temporary DB

You could have at least one bad/failing disk. So you're sure you're running 4.2.13? I would suggest once the resync completes you backup all data, power down and run the "Test Disks" boot option: http://home.bott.ca/webserver/?p=252

Definitely running 4.2.13. At least Raidiator and FrontView both say so. Will need to find a disk big enough to hold a complete backup before doing to test disks option but thanks a bunch for the good tip.
Out of curiosity, what makes you come to the conclusion that there is at least one failing disk?
(just mentally refusing to believe that these WD biz class disks could fail within a year when I have never had a consumer grade seagate fail within the last 5 years, urgh.....)

Your NAS thinking two disks are bad could indicate that they are. No need to backup data before running the "Test Disks" boot option. I just recommended backing up data ASAP if you can access it in case a few disks fail, this time for good.

There was a situation when two disks could be failed on the NVX, but that was on older firmware and fixed.

I just updated my NV+ from 4.1.6 to 4.1.8 so that I could use it with Lion in an iMac and AFP. The update went smoothly, but as soon as I tried to access it I got the message about CNID DB, which I have never seen before. It says switching to read-only mode. It does not seem to be fully consistent. I got the message first with the Lion machine, then did a file system check/reboot and went to an old Leopard machine and got the message. Immediately after that I did not get the message on the Lion machine and was able to access, then the message came back.

The Log only shows that no errors were found in the volume check. Incidentally - the logs seem to have switched to Swedish. I have switched them back.