Estas guardando mail y en la tabla nueva le pusiste de nombre email ... !!!
Código PHP:
mysql_query("insert into users (user,pass,mail,nombre,apellidos) values ('$new_user','$new_pass','$new_mail','$new_nombre' ,'$new_apellidos')");
Verifica que los datos que estas guardando sean del mismo nombre que los que estan en la BDD
Saludos !!!