The reason the AI can't build on Settlements you place on a map is that they're not aligned to the map grid. It's almost impossible to align one to the grid by hand, but I was playing around with some ideas and discovered this:

1) Create an area of flat terrain (all the same elevation)
2) Place a Berry Bush for Gaia in the middle of it
3) Add a new trigger with no conditions and two effects: first, Unit Heading on the Berry Bush for 180 (or 90 or 270 or 0 depending which way you want your Settlement to face), and second Change Unit Type on the Berry Bush to Settlement

When you test the game, you get a Settlement that the AI can build on ! The reason this works is that Berry Bushes are always aligned to the map grid when you place them (I don't know why but they are), so when you turn them to Settlements the Settlements remain aligned to the grid. You have to set heading to 0, 90, 180 or 270 to make sure the sides of the building are aligned to the grid too however.