I have a folder nested like:
Greatest Hits (folder)
Led Zeppelin (playlist)
When I plug in my Classic I click on the Greatest Hits folder to sync. On the iPod when I select playlist: Greatest Hits, it shows
The same works for having folder inside of folders.
It could be that you have an older 80GB Classic that does not support sub-folders. I forget when they added that to the iPods but I don't believe it's always been available.