1. sync your device to the software. select the device tab, select playlists, delete playlists.
2. only thing I can think of it to do wipe the zune and reset it. sounds more like a hardware problem, might just have to live with it.
Thanks for the suggestions, however, I have done both those.
The playlists no longer appear in the software but are still on the zune device. Wiping the zune is what created the playist error when I resynced to it. Somehow my entire library got messed up during the reverse sync and I had to start from scratch.