Re brewing the recipe: I've brewed several variations on JZ's recipe, and they all come out well. I think you need a good clean fermentation. The small amount of character malt really shows. I did JZ's and put a little wheat into it, and you can really taste it. I've tried munich and vienna and aromatic in small amounts and they all come out really nicely.
Some things to consider.
Hops: if you want hop flavor and aroma, you get a wonderful delicate character through the use of low alpha hops to achieve the bittering. If you want it completely malty, use higher alpha hops. My preference is the former, and I search out the freshest lowest alpha noble hops i can get and it develops a fantastic hop character.
Character malt: keep it low and subtle. 5% munich or vienna works well, but If you use a higher kilned malt, you need to go lower. Wheat similarly should be used lightly. Though it's not traditional, I've used 5% torrified wheat and still get a clear beer. It's got a stronger "wheat" flavor than wheat malt.
Yeast: I prefer the wyeast to the white labs, but it's much more powdery. Shouldn't be a probelm if you lager it well. If you ferment it down to 60, you get a beautiful clean kolsch. At 63 it's got this light "white whine" character that I really like, but might not be the best flavor in competition or the most accurate representation for kolsch. I ferment my kolsch down at 60, but I do the american wheat 63-64 to get that character (and help an otherwise boring style develop character).