When player 1 has placed a house on a city, can player 2 place his/her first house on a city in the same coloured area as player 1's house, or must player 2 start in a different coloured area?
Players can put their starting house in any city that another player does not have a house, including one that shares a region with another player's starting house (as long as its in one of the regions that are in play for that game).
The rules state:
Each player starts his network by choosing any city (not already chosen by another player) in the playing areas (chosen at the beginning of the game) on the map.
Players have to be able to play in the same region as another player because in a 6 player game, there are only 5 regions in play, and so at least two players will start in the same region.
Regions only matter for what areas are and aren't in play. They have no other effect on game-play.