I think this is due to the fact that the played songs are marked with "DONE". The Next Song command always tries to jump to the next song not marked with "DONE". You can either clear the song history to get rid of the DONE marker or if you don't care about being able to see which songs you have already played, go to Settings -> User Interface and disable the option Show DONE Marker.
Oh, and regarding the start over, you have two options, either set the Stop Mode in Playback Settings to Rewind or just drag the song position to the beginning in the waveform view (only works when playback is stopped).