What map script are you using?
For most scripts - that is, scripts that don't override the default civ placement function -, you need to change a variable in {civ 4 directory}\Assets\XML\GlobalDefines.xml
In this file, you need to change either or both STARTING_DISTANCE_PERCENT and MIN_CIV_STARTING_DISTANCE variables.
Try increasing the latter to, say, 20.