Well my DVD drive seems to be going bad so I can't boot from the setup disc for now, but the rmdir answer from @TuxRug inspired me to try an old trick, and it seems to have worked.
- In Windows Explorer, uncheck "Hide protected operating system files" folder option
- Browse to C:\ and rename the RECYCLER folder to say RECYCLER.bak
- Now delete RECYCLER.bak, and Windows immediately creates a new RECYCLER folder.
With a freshly created Recycle Bin, and the old corrupted in it, I simply did Empty Recycle Bin, and the problem has cleared up. No rebooting necessary.