Gave SFC a try but it didn't help us. We managed to find out what the problem was in the end.
The icons seemed to freeze after we'd loaded and then closed Internet Explorer. Even though we'd closed IE, it still showed in the task manager as being in memory. When we did an 'end process' on iexplore.exe, the desktop icons all worked again.
Have switched to Firefox!! Problem solved (well, worked around!)