Anzichè fare un <input type="submit"> fai un <input type="button"> sul cui onCLick chiami una funzione javascript: al suo interno fai i test che vuoi e se vanno bene chiami il metodo submit del tuo form, altrimenti non fai nulla (magari mostri un alert con la segnalazione di cosa non va).

Per testare la checkbox puoi fare una cose del tipo:
codice:
if (document.form1.checkbox1.checked == true)
  document.form1.submit();
else
  alert('checkbox non selezionata');
Ciao