Your problem is probably that there are files in the recycle bin which are marked as hidden or system files. To make these files visible, open your recycle, click on View, then Options, in the options window click on the View tab. Now in this tab the "Hide files of this type" option is probably selected, instead of that setting click on the "show all files" option. Its also a good idea to uncheck the "Hide MS-DOS file extentions" option, that way you know the full name of everything you are looking at.
Also you could try doing a search for a hidden file call ShellIconCache and Delete it then reboot. Make sure you set your system to show system and hidden files and then do a find files on your computer. Locate the ShellIconCache file and delete and reboot. Windows will recreate it on startup.
You can also try to restart in DOS or boot to a command prompt and enter Deltree / y c:\recycle
This will completely delete the recycle bin including all files. Windows will recreate it on the next boot.
It is advisable to BACKUP before trying the above.