I found that when I installed the extra dll files in to the civ program folders this may have been fine for base civ 4; however, as I was launching via the Beyond the Sword option I needed to put them in to that directory too. I suspect you might want to put the dll files in to the warlords directory. Hope that helps, I'm also new to Wine and Linux so don't shoot me if it doesn't solve your problem. It worked for me.
