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 
