A lot of magic can be explained away in some classes, parts of it can be removed. It would be a mistake I think to rule out what should be an iconic class for the setting, the Barbarian!
I think it's all right to tweak classes and powers a bit. Looking at all the classes, here is a list of tweaks I think could work.
Cleric (Warpriest)* - remove all implement powers
Fighter (Knight, Slayer) - fine
Paladin* - remove all implement powers
Ranger - fine
Rogue (Thief) - fine
Warlock** - fine
Warlord - fine
Wizard (Mage)** - fine
Avenger* - remove all implement and teleportation powers
Barbarian* - all elemental (fire, cold, thunder, etc) powers have their element removed (any extra damage from the element becomes untyped, any elemental resistance remains unchanged)
Bard* - remove all implement powers
Druid - no
Invoker** - fine
Shaman - no
Sorcerer** - fine
Warden* - all elemental (fire, cold, thunder, etc) powers have their element removed (any extra damage from the element becomes untyped, any elemental resistance remains unchanged)
Ardent - no
Battlemind* - fine
Monk - fine
Psion - no
Runepriest* - fine
Seeker* - fine
Artificer - no
Assassin* - remove all implement powers
Swordmage - no
* only one of these classes may be present in the party.
** only one of these classes may be present in the party. Player should be prepared for some prejudice against him, if playing one of these classes. It may be good for those who like a RP challenge, but bad for those not wanting to play with a handicap.
If you tell your players to be mindful of the setting, I think it will all work out fine. I for instance play a barbarian who has absolutely no "magical feeling" powers.
As far as races go, most can be reskinned as human. A short stocky human could be a dwarf, a young light weight boy could be a halfling, a strong and agile barbarian could be a half-orc, a woodsmen could be an elf. Dragonborn, Gnome, Drow and the like probably won't work for all classes, but a ** class player could choose something like Dragonborn if they were playing a sorcerer (or a drow dark pact warlock). They'd still look human, but you would explain away their racial traits with magic.
There are many viable variations I can think of that would work fine in a conan-like setting. I wouldn't try to make it exactly authentic, that limits both your and the players' creativity a bit too much. With sufficient amounts of reskinning, a party consisting of a Human Paladin, Half-orc Slayer, Halfling Thief, Human Warlord, and Drow Warlock would be quite fine, as would Goliath Fighter, Elf Monk, Human Ranger, Dwarf Warpriest, and Human Invoker.