Well I'm not sure how things show up on the new iPod Classic, but my 1st gen iPod nano lets me browse via Artists, or Songs, or Albums. So instead of going through directly to Albums, try going through to Artist, then Album, and then song list.
Also, have you checked to make sure that it's not set to shuffle all songs?