Put me in the "half-orcs are just fine" category.
If you want more data than the anecdotes of people on the boards with an axe to grind, this is about the best I can think of:
www.nyrond.org/turbine/charstat-people
It's a list of all of the Living Greyhawk characters in the Nyrond PC registry. Granted, it is self-selected as people voluntarily report their PCs and therefore probably overreports the PCs of people who are highly motivated and involved in the game--a casual gamer is less likely to put his PCs into the database. It is also, being originally a Nyrond database (also used by the Pale with a different front-end), skewed towards Nyrondese characters and players. (And, with half-orcs officially discriminated against in Nyrond for several years of game play, that may have had a slight effect upon the results). However, I can't think of a larger public survey of what kind of characters people actually play. It also has several advantages for our purposes. Living Greyhawk sticks fairly close to the RAW and only PHB races (plus, deep and tallfellow halflings, wood elves, grey elves, and a limited number of Sandstorm or special race characters) are available. Thus it serves as a decent comparison point for how popular various races are.
The raw data for non-retired characters shows human as the top choice (at 22.63%) and two (mechanically identical) human subraces in 2nd and 3rd place (7.7-7.3%). Half-orc comes in fourth at 5.93%. Dwarf follows at 5.52%.
That may be a bit misleading though since some reporting options split other categories. If you add "elf" and "high elf" together, you come up with 6.03%. Adding the mechanically identical "dwarf", "mountain dwarf", and "hill dwarf" together, you come up with 9.18% Add Gnome and rock gnome together and you get 4.68%.Add Elf (grey) and Gray elf together and you come up with 6.38%. Add all of the halflings together and you come up with 7.12%.
So, if you crunch the numbers to come up with more meaningful results, it is:
Human about 46%
Dwarf 9.18%
Halfling (all varieties): 7.12%
Grey Elf 6.38%
High (PHB) elf: 6.03%
Half-orc: 5.93%
Gnome 4.68%
Wood elf 4.09%
Half-elf 3.91%
If one discounts humans, and assumes that popularity corresponds to the mechanical strength of the race then half-orcs fall right in the middle. They're well below dwarves and slightly behind halflings and grey elves, but well ahead of half-elves. That seems fine to me.
However, if you want to make half-orcs more attractive, here is my suggestion (usable in whole or in part):
Orc weapon proficiencies. All half-orcs are automatically proficient in javalin, falchion, and greataxe.
Weapon Familiarity: Orc Double axe
+2 intimidate, +2 fort saves against disease.
+1 morale bonus to attack dwarves and elves
That avoids eviscerating the human advantage of the bonus feat (the compelling reason, other than "why play a short/skinny/ugly/bearded human when the real thing is mechanically viable" to play a human) or the human skill points (also a big advantage that helps to make up for the lack of darkvision, etc). And it gives half orcs what a previous poster described as the miscellaneous bonuses that make the package a bit more attractive.