I appear to have finally fixed this issue! I'm not sure if it's on 3.1 (which I now have) or not, but I did 2 things:
1) I removed all odd characters out of my playlist names, including a - and a » I was using
2) I changed the format of my MusicBee playlists to M3U instead of MBP. I did this in Preferences/Library/Playlists
Then I deleted all playlists on my Android and resynced and got no errors at all. It's a miracle!