It seems to be related to either the length of playlists, mistakes in the playlists, or the use of subfolders. It doesn't seem that fixing the play list fixes the sort order.
My playlists for albums all import fine. I think the largest album I have successfully copied over is about 24 files. The common thread for all these good playlists is that the playlist is in the same directory as the songs in the list.
But I do get playlists that are screwed up.
The latest was 65 songs long and had some mistakes in it (misspelled filenames). It also had songs from the folder I put the playlist in as well as songs from some subfolders. When I had fixed the mistakes, it still is misordered. I tried deleting the playlist from the phone, then deleting it from Play (it still listed the playlist as if it existed), then recopied it to the phone. I even tried deleting them and renaming the playlist to a new name and copying it back over. No joy. Funny thing is, it always imports in the same (incorrect) order.
There must be a memory leak in their m3u playlist file reader, I imagine related to reading subfolders.