What kind of NAS is it?
The issue is probably with the NAS itself, since it's claiming the path doesn't exist (but it does exist, and works after a retry sometimes, which makes no sense).
A Process Monitor log of what happens when the error message appears (and info on which filepath the error was for) should be able to confirm that, or reveal more details about what's going wrong.