Have you checked "Delete tracks that aren't on the auto-sync list from the device" under the 'Auto-sync options' tab for your device?

Have an iPod Touch 2nd Gen, and whenever I rename a playlist within MM, the playlist does not get deleted. The renamed playlist is synced with the iPod, and the tracks are added, but the playlist with the old name is also retained, along with all of its old tracks.

Wondering what I can do to fix this.