Found this fix also which helped a lot:
Recycle Bin Corrupted - Cannot Delete File or Folder - Vista Forums
IMPORTANT: The following procedure permanently deletes all files and folders which are already in the Recycle Bin (from all user accounts in the system) and cannot be recovered.
1. Open an elevated Command Prompt window. To open an elevated Command Prompt, click Start, click All Programs, click Accessories, right-click Command Prompt, and then click Run as administrator.
2. Type the following command and press ENTER: rd /s /q C:\$Recycle.bin
(This clears out the $Recycle.bin folder from the C:\ partition. You may have to do this for each hard disk partition in your system.)
3. Type exit to close the Command Prompt window.
Now check if the issue still persists or not.