This seemed to be a problem related to corruption or iTunes Match. When I pressed play in the Music app, it would shuffle through the playlist rapidly and not stop to play anything. There were some songs that would play, but not many. Annoyingly an astoundingly stupid song my kids enjoyed when they were two was a common song that would play.
Anyway, the resolution came when I used the Settings app:
- Settings -> General -> Usage -> (wait for calculations) Music
Then I swiped “All Music” and deleted it all.
From that point the Music app worked properly with iTunes match downloading songs as they were played.
This was iOS 6.1.3.