Found a solution - nothing worked until this:
1) Turn off iTunes Match (it took me 3 tries to get it to stick - it kept going ot ON when I would go back into settings). This was critical - it had to be off or this wont work.
2. Download iExploer, connect iPhone, open iExplorer
3. navigated to iPhone\Media\iTunes_Control\iTunes
4. Deleted the following 3 files:
MediaLibrary.sqllitedb
MediaLibrary.sqllitedb-shm
MediaLibrary.sqllitedb-wal
5. Deleted ALL of the playlist shown in that folder. I have about 12 playlist, over 100 were listed.
6. Performed a hard reboot on my iPhone (home button + sleep/wake button, hold until you see the apple logo)
7. Opened Music, went into iTunes and downloaded a free song. Waited for it to download, verified it was there (the only song listed)
8. Went into settings and turned on iTunes Match.
9. Went back into Music, the Cloud icon now showed a quickly moving blue bar under it and my music has been restored.
I did this on 2 devices and both are working. I'm wondering if it's a playlist issue on the phone. Good Luck everyone!