As far as I know, the AI always settles straight away when it can, so this seems odd. Unless there were barbarians placed on the map near the AI Settler (this will not happen in an unmodified game), or the AI was placed on unsettleable terrain (again, to my knowledge this should be impossible in an unmodified game), I cannot see any reason why this would occur. Perhaps you could provide a screenshot or savegame for us to be able to examine this more closely?
I loaded up the 4000BC autosave and checked world builder and couldn't find any other units other than my settler and warrior.Since patches refuse to work on my computer (no idea why), i'm using BtS unpatched. Is this a known bug without a patch?