Una vez mas excelente lo tuyo amigo.
Lo hice de forma que no importa el criterio de busqueda que empleen en el Form; que los resultados se ordenaran de manera Ascendente por apellido como en toda Guia Telefonica.
El Codigo quedo así:
Código PHP:
// Buscar registros
$consulta = "SELECT * FROM telefonos WHERE
nombres LIKE '%$nombres%' AND
apellido LIKE '%$apellido%' AND
prefijo LIKE '%$prefijo%' AND
sufijo LIKE '%$sufijo%' AND
calle LIKE '%$calle%' AND
puerta LIKE '%$puerta%' ORDER BY apellido ASC";
Mil GRACIAS otra vez. Saludos