For me, a coding exercise is more than just a way for me to see if the person can produce something that works. It's also a kick-off point for other questions. Often there are things the person will do along the way to a solution that reveals some lack of knowledge, so I keep my eyes peeled as they talk through their solution for these potential gaps.
One of the biggest problems now is that you have people who can even pull of FizzBuzz but don't know much of anything beyond how to get something like that working. They don't understand data structures, algorithms, or how a computer really works.
A simple coding exercise like FizzBuzz can reveal these gaps too, even if they get the problem right. The trick is to use their implementation as a way to probe their thinking.
For example, if they are just using a "sort" function, like in Ruby, ask them how it contributes to the runtime of their algorithm. Or, if they are loading a file into RAM instead of just iterating over reads on a file handle, ask them about it. Or, if they are iterating over the keys of a hash (h.keys), ask them how they think that works. (This recently revealed to me the candidate did not understand that a hash function was irreversible.)
None of the major gaps in knowledge I've found that separate mediocre from good candidates were found by just looking at their code and giving them a thumbs up or thumbs down. That's good for separating the mediocre from the morons. To find out if they're good, you have to probe.
To find out if they're great, well, that's another story entirely that is far afield from FizzBuzz :)
That's a lot, if you ask me - the morons usually make up the vast majority of candidates, so by filtering them out effortlessly at an early stage, you get to spend your time more effectively - identifying the great ones among those who at least hold a promise.
I've seen a few "will pick up [perl | c++ | java | whatever] as a I go" type guys. (Come to think of it... I've been that guy on occasion)
Incidentally, if you think Java programmers who can't figure out how to count the number of occurrences of the letter "a" in the string "Java java java" are bad, you should see how many interpretations of "advanced oral and written Japanese proficiency" we've had. Oh boy. Let's hypothetically say you're a recruiting company and you get a candidate as far as our door without disclosing that their exposure to Japanese is, I kid you not, "I loved watching Kenshin in high school" -- we will not be doing business with you again. Hopefully ever.