vfb,
Subtract 512 from the terrain value for the province that you want to allow as a starting province. For example, province 66's terrain value is 516 (SEA + NOSTART). Change it to 4. Any changes you make to the .map file will only affect new games.