I've not heard that explaination before. I've heard of using too much water in the mix, too much water in the cleanup and too much water evaporating through the slab, but never grouting too soon. If he meant that the grout wasn't allowed to "slake" long enough, he might be right.
Try the mild acid scrub Nathan suggested first. It's a lot easier than hand painting all your grout lines with a colorant (stain). Since this is a mild acid, allow it to sit on the grout for a few minutes, then scrub with a stiff synthetic bristle brush, repeating as needed. Rinse well with clean water and allow to dry. If you see progress, continue until the color is right and all the grout haze on the tile is gone.