iTunes Match is not required to address this, you just need to learn how playlist editing works:
If you create a brand new playlist directly on the iPhone, the playlist will transfer to your iTunes library on your next sync. However, if you buy music directly to your device and put it into a new playlist without syncing these songs back to iTunes first, then such changes may not "stick" when you finally get around to re-syncing. Music you buy directly to your device are kept in sort of a limbo state until you re-sync, so I'm not surprised that it fails if you add such purchases to a playlist before transferring them to your library.
If you want to edit an existing playlist directly on the iPhone, the changes you make will not be saved next time you re-sync to iTunes. I suppose this is by design to prevent you from screwing something up. Instead, if you want to edit an existing playlist, first create a new (empty) one and add the desired playlist into the new one. Then edit the new playlist as desired, and when you sync back to iTunes replace the original version with the edited copy, or keep both copies.