Concept albums should not only all be about the same thing, but thhey should also tell a story, not only through lyrics, but also through various musical devices. There should be an introduction, development of a conflict, and a final resolution. One could even consider different songs from a concept album as different movements in a symphony.
Prog rock generally lends itself best to concept albums as prog tends to explore the same musical theme in many ways, and tends to be more lengthy and developed than most other rock genres. Metal and goth rock tend to lend themselves to concepts as well, as both genres tend to be very.....dramatic. Industrial also lends itself to concept albums (sometimes) because industrial music tends to both be dramatic (gooth influence) and revisit the same themes over and over (electronica/prog influence). I would claimm, for example, that Skinny Puppy's most recent album, The Greater Wrong of the Right, was probably a concept album related to the Iraq war. This contrasts with other anti-war albums, such as the above-mentioned Green Day album, because Greater Wrong set up a distinct narrative, and kept a consistent theme both lyrically and musically.
One that's not beenn mentioned yet, of course, is The Who - Tommy, which was an awesome album and I totally forgot about it earlier.
That deaf, dumb, and blind kid sure plays a mean pinball.