Contrary to popular belief, the gapless setting you see in iTunes does not turn an album into a gapless album. The "Part of a gapless album" setting in your tags only tells iTunes that you do not want it to use the cross-fade feature on the album, just in case cross-fade is enabled. That's all it does and has ever done -- it was never intended to make the album gapless. Furthermore, it only works in iTunes and not on the iPod since the iPod does not have a cross-fade feature (though the new Nano does, so maybe this setting works on the 4G Nano with respect to cross-fade).
Gapless playback is determined when you rip a CD (or add pre-ripped songs into iTunes). If an album is not playing gaplessly, you can try re-ripping it, or supposedly you can check the "Part of a gapless album" setting and then un-check the setting to force iTunes to scan the album again (not sure if that really works though). Also, if you are ripping CDs that were burned from iTunes or some other media player, it is possible that the burning process inserted a short gap between songs, and that gap cannot be removed if you try to re-rip the CD.