C'è un problema concettuale... una volta che hai reso qualcosa disabled, devi avere anche qualcosa per renderlo enabled di nuovo, perché una checkbox disabled non cambierà il suo stato (checked/unchecked) al click.

Una possibile soluzione potrebbe essere usare due radio button, uno per la prima scelta e uno per tutte le checkbox clienti.

codice:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>Documento senza titolo</title>
<script type="text/javascript">

var allChecks;

function oneChecked() {
  var oneChecked = false;
  for (var i = 0; i < allChecks.length; i++) {
    allChecks[i].disabled = false;
	oneChecked = oneChecked || allChecks[i].checked;
  }
  return oneChecked;
}

window.onload = function() {
  allChecks = document.getElementById('clientlist').getElementsByTagName('input');
  for (var i = 0; i < allChecks.length; i++) {
    allChecks[i].onclick = function() {
		if (!this.checked && !oneChecked()) {
			  this.checked = true;
		}
	}
  }
}

function unselectAll(checkContainer) {
  document.getElementById(checkContainer).style.display = "none";
  for (var i = 0; i < allChecks.length; i++) {
    allChecks[i].disabled = true;
  }
}

function enabledClientList(checkContainer) {
  document.getElementById(checkContainer).style.display = "block";
  if (!oneChecked()) {
    allChecks[0].checked = true;
  }
}
</script>
</head>
<body>
<form id="checkboxtest">
  <input name="radiobutton[]" type="radio" value="NoClient" checked onclick="unselectAll('clientlist');" /><label>Nessun Cliente</label>

  <input name="radiobutton[]" type="radio" value="SelectClient" onclick="enabledClientList('clientlist');"  /><label>Scelta Cliente</label>

<fieldset id="clientlist" style="display:none;">
  <legend>Client List</legend>
  <input type="checkbox" name="clientChecks[]" value="12098" />Cliente 12098

  <input type="checkbox" name="clientChecks[]" value="34567" />Cliente 34567

  <input type="checkbox" name="clientChecks[]" value="41298" />Cliente 41298

  <input type="checkbox" name="clientChecks[]" value="8276" />Cliente 8276
</fieldset>
</form>
</body>
</html>