I ended up saving my playlists as M3U8 and simply renaming them to M3U. Even though technically M3Us can be only ASCII, android still reads them even if they are UTF8. Also, if for any reason android decides to "fix" playlists to non unicode and stripping out lines that contain unicode characters while doing so, then I just set file permissions on all playlists to read-only.
Model.... Samsung Galaxy S III (Verizon)
ROM...... CyanogenMod 10.1.3