Well I know the shield mean that the file needs admin access to change, but as for the recycle bin, I'm not sure. My best guess would be that maybe the file was thrown away and then restored?
Try changing the icon manually via the properties of the file and then saving the settings with a log-off/shutdown.
Well it happens to all the files saved on my desktop. And it happens repeatedly - so it can't be because they were deleted and restored (not by me anyway). It doesn't happen to folders or shortcuts.