I had this problem on my old computer, just disable the recycling bin and restart, then enable it again and restart. I was using vista so here are the steps I used:
Click on "Start" and type "gpedit.msc" (without quotes) in the Search box.
Click on the "gpedit.msc" program in the search results. This will open your group policy editor.
Click on "User Configuration > Administrative Templates > Desktop."
Scroll through the list on the right-hand pane until you see "Remove Recycle Bin from Desktop." Right-click on it and select "Edit."
Look under the "Remove Recycle Bin Icon from desktop" options. Click the box that says "Enabled." This will enable the group policy to prevent the icon from displaying. Restart your computer for the change to take effect.