Are they static or smart playlists?
Smart playlists have to be removed from Firefly using the smart playlist editor.
Static playlists are copied from iTunes library files or .m3u playlist files. To get rid of these you'll have to find the offending xml/m3u file and delete it.
Once you've removed the offending file / settings, run a full scan.
A more drastic step would be to also delete the DB (songs.db / songs3.db) before running the scan.
Just out of curiosity, do these old playlists show up on the M1001?
If No, then it could be an iTunes problem, not a Firefly problem. You can check by using the Java Firefly client.
FYI, The java Firefly client can delete playlists from Firefly's DB
2 x M2000's
Infrant ReadyNAS NV+ with Firefly svn-1676
NSLU2, 500GB Maxtor One Touch III, uNSLUng 6.8, Firefly svn-1696
music library in FLAC format