So it looks like my playlist issues were based on a couple of problems.
1: I had my WMP 11 storing music and playlists etc. on a remote share. This appeared to make things a little strange and will need to be revisited.
2: The sync only playlists were being troublesome especially the All Music one. I now filter out the sync only playlists and ignore them and all seems well.