Yeah first thing I did was check if shuffle was on. I removed the app and reinstalled and now it's fine.Ohhh, let me test, you sure Shuffle is off when you play music?
Update : Tested, works fine, I'm guessing Shuffle might have accidentally turned on.