I think this is the one small feature the iPod on the iPhone is truly missing... I have plenty of playlist folders to organize my playlists, and none of them go on the phone.
While they're at it, can we add live updating of smart playlists on the iPhone?
It would also be cool if we could create smart playlists like we can in iTunes. The don't need to be permanent, as even a temporary smart playlist would help out a lot.