Or........... if the grout is just badly discoloured try painting it with neat thick bleach and leaving for a couple of hours, repeating if needed, use a 1/2 in paint brush, cheap one, works for me with little effort. Also if you accidentally remove the glaze on the tile when removing the grout mechanically then that area will also get grubby quite quickly as it is porous and not as resilient as the grout to stains etc..
Paul.