Have you run the chkdsk to fix file system errors? I had that problem with a couple of files I couldn't delete before, and it was due to some kind of disk corruption... running the error checker fixed the corruption and I could delete the files.
I actually ran it twice (once a little while after it happened and once again today). The first time I ran it for some reason it deleted two folders (one had mp3s and the other had installers) and I still couldn't delete anything.
After this last time nothings changed. The thing is if I go to the Recycle Bin > Properties > Global and check the "do not move files to Recycle Bin" box it allows me to delete stuff, but then again once it's gone, it's gone.