Just to close this completely. Android's media scanner (at least on my Xperia) is not perfect when it comes to playlists. I left it ages, it recognised that the sync had removed the old playlists, but not that it recreated them, I tried using the default path /Playlists and also tried /Music/Playlists. Neither really worked too well, it always showed no playlists afyer syncing.
I also tried Media Go, which comes with the phone, same problem, so it's clearly not a MM4 problem.
What DID work for me, using using this Android app, which kicks of a manual refresh of the media database:
https://market.android.com/details?id=c ... diascanner