Greetings!
Hello Simon!

I think that you should consider the following races:
(1) Minotaurs: These can be reasonably intelligent, and you can even change their alignment.
(2) Ogres: Ogres can make an interesting addition to the campaign world. They make good soldiers, and also put a different spin on the area's labour force.
(3) Quaggoth: Shaggy, white, bestial humanoids. What if they not only live underground, but on the surface as well? Assume they have quasi-vampiric natures, and gain a special rage ability at night, under the light of the moon. They could have Light Sensitivity as well.
(4) Gnolls: Make them intelligent, and provide them with a culture based on the ancient Aztecs of Central America.
(5) Trolls: Change the stereotype entirely. Assume Trolls are an ancient race of highly magical beings, who have a highly developed culture, like that of ancient Egypt. Perhaps they make pyramids from a strange black stone that has magical properties influencing ley-lines.
(6) Centaurs: Forget the standard. Make these guys like the ancient Dorians. The Dorians were an advanced Indo-European tribe that swept in from the Eurasian steppes and crushed Greece. Make the Centaurs intelligent, advanced in weapon skills, and savage in wrath. Make them excellent in war, and have them enjoy drinking, feasting, and crushing other races under hoof. Make them build great arenas, and sponsor gladiatorial games. make them an awesome terror in land warfare, with vast hordes that burn, rape, and conquer their way across the continent. Make them afraid of the sea, and suspicious of ever travelling by way of the sea. Provide them with an Imperial Roman government, and make them arrogant and prideful of their status as superior creatures to other races.
I hope that you find my suggestions helpful, Simon.
Semper Fidelis,
SHARK