I say keep the move silently, and drop the spot/search/listen bonus for the grapple bonus.
How about this: drop Move Silent, and drop the Search bonus (not the bonuses to spot and listen, though). In exchange, give the grapple bonus. With these changes, their racial traits look like:
Gutterkin Racial Traits
• +2 Dexterity, -2 Intelligence. Gutterkin are quick and strong for their size, but don't do well when in comes to thinking ahead, or thinking in abstracts, or thinking at all.
• Small: As a Small creature, a gutterkin gains a +1 size bonus to Armor Class, a +1 size bonus on attack rolls, and a +4 size bonus on Hide checks, but he uses smaller weapons than humans use, and his lifting and carrying limits are three-quarters of those of a Medium character.
• A gutterkin's base speed is 30 feet. Gutterkins' speed has helped them get out of danger on more than one occasion.
• +2 racial bonus on Spot and Listen checks. Having been forced to live in particularly hazardous areas, gutterkin have learned to always be wary of potential hazards.
• +2 racial bonus on grapple checks. Gutterkin are scrappy, and more pugnacious than seems healthy for a creature of their size.
• +1 racial bonus on all saving throws. Survival of the fittest is the name of the game for gutterkin, and those that are fittest are the ones best able to shrug off the poisons, diseases, falling rubble, collapsing shanties, and other accidents that plague gutterkin communities.
• Automatic Languages: Common, Gutterkin.
• Bonus Languages: Dwarven, Elven, Orc.
• Favored Class: Ranger. A multiclass gutterkin’s ranger class does not count when determining whether he or she takes an experience point penalty for multiclassing.
I'm pretty happy with this arrangment. I got rid of search not only for mechanical reasons, but because they really shouldn't be getting bonuses on Int based skills. Anyway, what do ya'll think of them now? If they still seem a little out of balance, what I'll do is give them Move Silent back, but change their +1 to all saves into a +1 just on poisons and diseases.