Odd...a search for Foo Fighters doesn't pull anything up. But if you go to Music --> Alternative, there's a small banner ad for their upcoming album pre-order. Clicking on that and then on the artist arrow icon takes you to a page with a bunch of their albums.
The iTunes Store has definitely gone nutty today.
It looks like some store preferences for these artists are messed up. They don't show up in a search and are missing from the main alternative page, but I've gotten to both of them using roundabout methods like you described (i.e. looking under an "iTunes essential" collection and clicking on them).