Does this work largely because Conan is a very low magic game?
That certainly has something to do with it, but I also think the class design helps a great deal. In order to multiclass, the only limitation is the GM (for example, I can't see a Barbarian multiclassing as a Pirate if the Barbarian has never been on the sea). Other than that, though, it's easy to multiclass.
Multiclassing provides skills needed to overcome problems. It's easy to multiclass, and characters with INT bonus can put some of their skill points into Cross Class skills without having to pay double.
The game is well designed to fit Howard's Hyborian Age.
For example, Conan became a thief in his early years, when he first set sandled foot into civilization. This made the character a Barbarian/Thief multiclass.
Conan, in the stories, was really more of a second-story man. You never see him picking locks or fiddling with traps. He uses his Climb (class skill for Barbarian) a lot to get him into less guarded areas.
In the Conan game, although there is a thief class, it's not necessary to be a thief class in order to be a thief. Conan could Climb, and he stole. That made him a thief--not his character class.
The same goes for priests and mages. In the Conan game, neither of those have a class. For example, the Pirate captain who is worshipped by native islanders, the Mercenary commander who leads fiercly loyal troops, or the Scholar-classed character who has studied the ancient texts and foretold the coming of an ancient god, all can be considered priests.
Yes, there is magic in a Conan game. Read any Conan story, and it is almost guarranteed that some sorcery will be in the tale, if not the focus of the plot. But, magic is used much differently than it is in a normal D&D game.
A good example is the location of my current game: An under-hill cave complex that serves as the fort/HQ for the bad guys.
In a D&D game, this place (since my game is low level) might be full goblins and kobolds, mayber a goblin shaman, a bugbear, a few hoboblins, and then a lot of extra stuff, here and there: gelatinous cube, giant weasle, giant spider, one skeleton and one zombie, etc.
But, in my Conan game, I packed the place with enemy clan members (human, barbarian classed), a few envoys from a far-off realm, and the giant spider which the baddies use for sport and prisoner interrogation. The one sorcerer in the place knows only one spell--a powerful spell that calls on the power of a demon to bring in gaseous beasties.
The D&D adventure might include several types of baddies for the PCs to face. In the Conan adventure, it is much more likely that the single sorcerer will call forth only one type of unnatural being for the players to fight.