Sin ver la consulta, no va a ser fácil ayudarte; sin embargo, creo que solo estás haciendo la búsqueda por el campo del nombre y no del apellido, suponiendo que los tienes separados. En esa situación, la solución consistiría en anidar más condiciones considerando otros casos, como búsqueda solo por apellidos, por apellidos y nombres, por segundo apellido y nombres, etc.
Por cierto, esto debe ir en el foro de base de datos, no en el de PHP.
