I have the same or similar issues. I just tried to play an album from Apple Music (not part of my "owned" music), and it started on the third song. I manually restarted on the first song, and it is now working. I have seen this before and at one point thought that shuffle was on, but it wasn't.