I just had this same exact thing happen, only I'm afraid to reboot, or certainly not do a disk cleanup. Mine also shows the desktop icon full, but opening the recycle bin shows it's empty, and if you empty it anyway, it also asks "are you sure you want to delete WINDOWS?"
Quoted earlier, "Is it only the recycle bin desktop icon that says it's full or also the icon in explorer? Open explorer and check to see if the recycle bin there is also full." -- I don't know what is meant by the icon in explorer. How do I check?
Thanks!
~Alan