Same issue here. It's always the first song which is played in shuffle mode.
If I try to select manually a song, the next track will still be the first song of the list. And the full list will play in same order oO
Sony support told me it was because my song started with " . I changed for a track starting with a number but the issue was the same. Maybe the song should start with a simple letter, I will try it someday.
I do not want to use this 1 second long track trick. What would be really good from sony would be to upgrade firmware to fix the tons of bugs the device is filled with.