Nerubian and Dragon+Dragonspawn were kinda done in Spiderqueen and RotD, although something more complete would be nice. Goblin and Demon have been done (and are in Race Champion Wars). Murloc+Mur'Gul are more or less the Naga (which have been completed by other people). Trolls are in that one set of 4 races, Tales of Rejuvenation or something (Chaos, Troll, Dweller, ya know?). Personally I was going to make the Draeni, being one of the last half-races no one did, and IMO its best if theres only one version of a race (you can do it if you want of course, i'm just saying). Kobolds (Or Underground Denizens) would be really unique, and I've never really thought of them. You could also try Centaurs or Furbolgs.
Actually I would vote for knolls, but they're not on the list, so I voted for the Nerubian. However, Nerubians have been done so many times before on other altered melee maps that I suggest you go with something different if you wish to stay original. -VGsatomi
id say draeni, casue they havent exactly been done well b4, but they need sum hero models and a few other models, like maybe a draeni riding one of those red lizards.