I managed to fix this problem myself. As per item 1 in
http://support.microsoft.com/kb/555644. We had a time synchronisation problem as the NAS was not using the AD domain controller as it's NTP server. Changed the NTP setting on the NAS to point to the DC and it is now working. (I think I had to reboot the NAS for it to take effect). Now to go and correct the time settings on our domain as it's running about 7 minutes fast. :)