This is definitely a bug with my 5G iPod as well, which I just ordered last week as a replacement for my 4G (dead HD).
As has been mentioned previously, this only happens when you have multiple songs tagged to one artist, with at least one of the songs tagged to one album, and the remaining songs with their album field blank.
When this happens, after selecting the artist, the iPod will skip the album selection screen, and display only the track(s) of the lone tagged album for that artist. I have been able to replicate this bug with only 2 songs under an artist (one tagged with an album, one not), also with multiple songs tagged under one album and one not tagged, also one song tagged with several untagged. It only happens when there is only one album for an artist.
I have also noticed something else in the behavior of the iPod that is very similar to this bug. If all the songs under one artist are tagged with the same album, it will skip the album selection screen, going immediately to the track list for the album. I don't know if this is an intended feature or not.
Also, if you hold down the center button while on the artist screen, selecting an artist that exhibits the album skipping bug, in order to add all of the songs from that artist to the On-the-Go playlist, all of the songs from that artist are correctly added, not just the ones from the album that gets skipped to.
There is also another bug. When navigating through the artist selection interface, after selecting an artist, and then selecting an album (or All), and then hitting Menu twice (or once if you picked an artist with the album skipping bug), the Artist's name will be incorrectly displayed at the top of the Artist selection screen instead of "Artists." Furthermore, when selecting another artist, the same Artist's name will be incorrectly displayed at the top of the new artist's album selection screen.
The album skipping bug can be temporarily "fixed" by tagging an otherwise untagged song with a space in the album field, or with the correct album, as having at least 2 albums under an artist resolves this issue, as I mentioned earlier.
I haven't yet found an Apple discussions thread on this problem, though I haven't been searching extremely hard.
I also hadn't yet applied the most recent iPod firmware updater, until about an hour ago, and this does not fix the problem.
Could someone please report this issue to Apple? Or point me in the direction of where I could? It seems like it would be an easy enough thing to fix, and something should really be done about it, as it is quite irritating.