robbie wroteYour 4th paragraph answered your question (statement) in paragraph 2.
Result of play is dead ball, runner out for leaving early. Your choice coach..................
Speaking ASA, according to the interpretation linked to above by youngump, the coach's choice option does not nullify the runner being out for leaving early. That out stands, regardless. And, since the leaving early resulted in a dead ball, there are no other aspects of the play to be considered. If there are other runners, they receive the base award, and the batter is awarded a ball. The runner who left early is out.
Also, argodad, what you were missing was the credibility of Referee on softball rulings is worse than your average coach.
Did Referee specify a specific rule book?