Seems like the database migration is not working. The problem is that the database structure needed to change in 3.7 to enable iCloud sync and it is no longer possible to access the old sort order field used up to 3.6. The migration tries to take care of it but does not work reliably.
My suggestion: please load a backup where your order is correct. Once you are on version 3.7 this will not happen any more. The problem is only the update from 3.6 to 3.7.
stevebarry Seems like when you updated your devices the sort order got changed in a different way on each device. Then you enabled iCloud sync which tries to match up your playlists but fails as the same playlist has a different sort order on each of your devices.
Again: Restore a backup on one of your devices and it will correct all connected devices automatically.