If you are shooting under artificial light it is possible that the camera had to push one color very hard to bring it in line with the others. For example, the shop lights in Iraq were very red. The red was about two stops over the blue and green. Using a cooling filter in addition to auto white balance allowed me to get decent photos with a D2X. Auto white balance on its own would amplify the blue and green by the two stops and cause them to be very grainy. Adding a filter mechanically balanced the light so the camera didn’t have to over compensate.
Photograph a white or grey target with auto white balance set to daylight. The histograms may show one channel much lower or higher than the others. You may need to bracket exposure to see how many stops your camera is fixing. A filter can help force the camera to stop over pushing one or two channels.