Creo que la solución al problema se puede solucionar así según veo.
1.- Una cosa que he visto es que algunos usuarios ponen varios espacios en vez de uno para separar. Pensando en esto deberias hacer que, usando eregi_replace(), se cambiarán todos los espacios dobles, triples o más por un solo espacio:
$varios_espacios = " +";
$cadena = eregi_replace($varios_espacios," ",$cadena);
En este caso el signo más luego del espacio en la expresión regular significa que el espacio se puede repetir una o más veces.
2.- Borramos los espacios blancos al principio y final de la cadena usando la función trim():
$cadena = trim($cadena)
3.- Separamos la cadena donde esta el espacio con explode():
$cadena = explode(" ",$cadena);
4.- Ahora la cadena es un array con dos elementos si ingreso dos nombres. De todas maneras debería considerar contarlos porque ya que estamos tan internacionales te puede tocar alguien de un país que no use los dos apellidos (Como los alemanes).
Para acceder al apellido paterno:
$cadena[0];
... y al materno:
$cadena[1];
5.- Despues de todos estos pasos realizas la validación por separado usando un if como este:
<span class="codigo"> if(funcionvalida(apellidopaterno)&&funcionvalida(apellidomaterno))
{
echo "OK";
} </span>
En todo caso como dije sería bueno considerar que alguien puede poner un solo apellido.
Además creo que tendrás problemas porque tu validación no acepta la letra ñ ni caracteres acentuados. En todo caso si esto va a ir a una base de datos en algunos casos sería bueno indicar si admites o no acentos aunque lo de la ñ no puedes omitirlo.
Una segunda opción seria que simplemente hagas trim y luego de esto reemplaces el espacio con un caracter x como # y en la validación incluyas este caracter como valido y luego lo vuelvas a poner como espacio.
Espero que te sirva!