When I set all start locations for all 8 players, then set all AI but 1, and randomize start location, I still always end up in 1 of 2 locations. How can you make it random like a regular melee map?

Maybe you could randomize a switch to decide where the players start?

Can you take a picture of the Forces page for us? You must have something off.

The start locations within each force are random, if random start position was checked for that force.
If you are in force 1, you will never start on a start location of a player in force 2.

So, in a melee map, all players are in the same force.

If you add an ai, you still can put all players into 1 force. But you may have side effects (doesn't work with Blizzard's staredit) like that you cannot switch the slot in the lobby. Make sure that there is a location over every main base and every player should execute an ai script.

If you run into problems, you can just use switches to randomize where you create the building/units/... like badcop mentioned.