Did you definitely use the command line to delete the folder?
One behaviour that has struck me as strange a few times on OS X is that if you are working in a folder in the Terminal but then delete it in the Finder, you can continue to work with the folder perfectly happily in the Terminal. Even in it's new home within the Trash.
If you try to open the Trash in the Finder and access anything in there you'll just get an error, but within Terminal you are able to work with the same files quite happily. You can even launch them from there and continue to work with them in other applications perfectly happily (for example opening a txt file in TextWrangler).
Also if you type "open ." in the Terminal it will open the folder in a Finder window and everything will look okay right up until the point you try open a file at which point the Finder will tell you "The document XXX can't be opened because it's in the Trash."
To make things even stranger, even though other applications will identify the path to the folder and its contents as ~/.Trash/foldername, if you type pwd in the Terminal it will still think it's at the previous location.
If you hadn't rebooted I would have suggested right-clicking on the window title to see if the folder in the Finder window is where you though it was. But now that you've rebooted... :)
Finder.