Jason,
When asking about Nikon autofocus, you unfortunately have to divide the question in two:
1) How quickly does it focus with AF-S lenses; and
2) How quickly does it focus with lenses utilizing the physical contact, i.e., where the camera rotates a pin in the lens mount?
With AF-S lenses, the D200 focuses very quickly, as quickly as any other. It's ability to track moving subjects is very good, but not as good the D2x. (I have both.)
With non-AF-S lenses, the D200 focuses more quickly than any Nikon other than the "pro series," e.g., D2x, D2hs, etc. If you are shooting something other than sports or birds or the like, it's fine. But AF-S, like Canon's USM, is superb.
In response to your specific question, Nikons supposedly do not autofocus with maximum apertures smaller than f/5.6; but I have both the D2x and D200 focus when the maximum was smaller when I've used AF-S lenses. The focusing is uneven, however, and you can count on continuous focusing only with lenses that have a maximum aperture of f/5.6 or larger. That is my experience, YMMV.
The Fuji S3 body had all sorts of issues that I'm sure kept many people away, such as the batteries used, the slow focus, the very low shutter speed at which the flash would sync. The S5 promises to be so much better if it makes use of all of the D200's advantages. Still, it uses the same sensor as the S3 which, although very good, probably does not have the advantage over other sensors that it once had. Both Nikon and Canon sensors have gotten better.
Best bet to see for yourself is to go a store, bring an f/4 lens and teleconverter and see how it does. BTW, I think only the Canon 1D series (including the 1DsMkII) claim to autofocus with lens having a maximum aperture of f/8.
I hope this is of some help; and welcome to the forum!
Joel