Yeah, I thought that the problem is with the Windows (most likely it is), but I can't think of anything that can do this...
1) The problem is from multiple computers (2 Win7, 1 WinXP)
2) The restarting of the NAS server usually solves it after a few (1-2) retries, without changing anything on the Windows - and it solves this problem on all of the computers
btw no, I haven't changed anything, for the Windows Update, I can't guarantee, but for the WinXP comp, that has the same problems, I'm sure that it's settings are the same (since WinXP is only getting security updates AFAIK, and even those are rarely released)