I want to destroy all of a player's units when he leaves. Here is what I have:

All triggers are ticked for All Players.

CONDITIONS:
Always
Current Player commands at least 1 [any unit].
ACTIONS:
Modify death counts for Current Player: Set to 1 for Cave.
Preserve trigger.

CONDITIONS:
Player 1 has suffered at most 0 deaths of Cave.
ACTIONS:
Kill all [any unit] for Player 1.

etc. for the other seven players

CONDITIONS:
Always
ACTIONS:
Modify death counts for Player 1: Set to 0 for Cave.
Modify death counts for Player 2: Set to 0 for Cave.
Modify death counts for Player 3: Set to 0 for Cave.
Modify death counts for Player 4: Set to 0 for Cave.
Modify death counts for Player 5: Set to 0 for Cave.
Modify death counts for Player 6: Set to 0 for Cave.
Modify death counts for Player 7: Set to 0 for Cave.
Modify death counts for Player 8: Set to 0 for Cave.
Preserve trigger.

But everyone has their units destroyed immediately after the game starts. Anyone know what's up with this?

When a player leaves his units are given to player 12. So the best solution is to always kill all units for player 12 (neutral).

What yoonkwun said.

Also keep in mind that the death counts of leavers are not set to 0 so this method won't detect leavers.
If you need to know the player number of a leaver just check for controls at most 0 [any unit].
If players can have 0 units at a point in the game while still being alive/present it gets a little complicated.
Ideally you let every player set his own dc to 1 and then player 8 (must be computer so he's always there) clears it. And when you detect a player with 0 dcs then you know he isn't there because absent players can't set their own dcs.
If you can't have a computer at slot 8 it gets even more complicated. Just ask if that's the case and give your exact setup.

It's a phantom map with up to 8 humans. I need to know when the phantom leaves so the other players can win. The phantom has a dc of 1 for a unit. So could I check if a player has dc 1 for that unit and controls 0 units at anywhere and then cause victory for everyone else? Or would the trigger not run because he has left the game?

All Players
Conditions:
Player 1 suffered 1 dc
Player 1 controls 0 [buildings]
Actions:
Win

Copy 8 times and replace Player 1 with each player.

Yes, Currently Player Commands 0 Any Unit... Current Player Deaths = 1... blah blah blah works fine... For future info if ur making a map and u dont want to kill every unit when a player leaves... using kill all *specific unit* for p12 preserve trigger works good too