As mentioned, it can happen with really long paths. Shortening the name of the folder, and/or parent folders if it doesn't disrupt anything, to a single character can help. If there's an invalid character, might be able to rename the folder, then try to delete.
Or perhaps
rd /s "folder name"
from the command line. Just be sure to include the quotes if the folder name has spaces in it. Gotta be careful, don't want to be deleting or renaming the wrong folders.
does using a dos shell work? I've found that when windows decides some folder is too important/doesn't exist, running a command prompt usually does the trick.
Otherwise, a dos boot disk or a knoppix livecd work too
was there anything weird about how this folder was created? (ie. a torrent or some other automated way that may include a special character) Special characters can really mess with windows.
My personal favorite is using alt+255 in a directory name. It looks like a space... but it isnt a space.
C:\temp>mkdir "del[alt+255]me"
looks like C:\temp>mkdir "del me"
fun times...
Edit: Never mind... I guess they fixed that in one of the Service Packs (winXP)..
I swear it worked... honest!