Yes, the half-elf is underpowered. According to D&D design staff Mike Mearls and Jesse Decker, as well as a Wizards of the Coast web poll, the half-elf is the weakest core race in D&D 3.5:
The half-elf is the least powerful race, because it is an elf with the weapon proficiency, secret door detection abilities, and racial ability adjustments removed and the bonus to Spot and Listen reduced. In return, the half-elf gains a +2 bonus to Diplomacy and Gather Information checks. These bonuses are useful only for a narrow range of characters – low Charisma characters and those who do not have Diplomacy and Gather Information as class skills gain little benefit from it since these skills operate against static DCs rather than opposed checks. In an opposed check, there's always a chance that you face an untrained or penalized foe, making any sort of bonus useful. Since both Diplomacy and Gather Information can be used untrained, they are poor investments unless you can use them to routinely beat high (20+) DCs. If anyone in the party aside from the half-elf invests in those skills, the half-elf's bonus is largely useless.
The ability to count any class as favored is a minor edge, especially compared to the human benefits. In comparison, the elf's secret door detection is useful to any character, while Spot and Listen are useful in almost every encounter.
Mike’s answer is correct, not because he chose the weakest race but because he demonstrated that the half-elf’s puny bonuses don’t compare at all with the other races. One of the not-so-obvious purposes of this question is to see how the potential developer deals with the word “weakest.” There can be all kinds of weaknesses in a roleplaying product, but the developer's job is to focus on the power level of game elements -- which means that interpreting this question as an analysis of a race’s combat ability is important.
Other popular answers to this question include the gnome and half-orc. While both of those races have their limitations (gnomes are mostly overshadowed by halflings, and half-orcs are severly limited in their choice of classes), both can shine in specialized builds.
As for how to balance it, I'd give the race +2 Charisma, -2 Wisdom. This takes the half-elf from a reasonably good bard to an excellent race of sorcerers and charismatic (if impetuous and short-sighted) military leaders. The Wisdom penalty is not a big deal for sorcerers, who get the good Will save anyway, and the Alertness feat from the sorcerer's familiar compensates for the Spot/Listen penalty. They make poor clerics, but this fits with their mixed heritage. They don't truly belong among the flock of with any one race's deities, and sharing the traditions of both peoples makes it more difficult for them to accept any one religion as the one true faith.