A ver, lo que respondí a la primera cita es que debes estar llamando a la función que valida desde el botón de submit ¿es así?
para que no lo envíe tras el return false de la funcón debes llamar a la función desde el propio tag del form en el evento onsubmit
<form name="form" action="loquesea.php"
onsubmit="return validar()">
Respecto a lo segundo lo más sencillo es que crees una variable global en javascript que inicialices a 0 y se incremente cada vez que se marque uno de los checkboxes. Como se necesita que esté seleccionado al menos uno compruebas en la función que esa variable sea igual o mayor que 1.
Algo así
var idiomas = 0
function validar(){
var fr=document.forms.form;
var error = fr.error.value;
if(fr.nombre.value=="")
{
alert(error);
fr.nombre.focus();
return false;
}
if(idiomas ==0){
alert('debe seleccionar al menos un idioma')
return false
}
}
y a cada uno de tus checkbox le agregas lo siguiente:
onclick="this.checked ? idiomas++ : idiomas--"
<input type="checkbox" name="to_lang[]" value="catañol"
onclick="this.checked ? idiomas++ : idiomas--" />
Con esto que le agregues a los checkbox incrementará en 1 el valor de la variable idiomas cuando se seleccione y la decrementará al des-seleccionarse