Fallo al ejecutar en PHP una SQL con LIKE (escapando clausula LIKE)

[ElJavista]

SELECT * FROM tabla WHERE criterio LIKE "%Telefono_Cliente = '123456' AND ( Nombre_Cliente = 'pepito' AND Apellidos_Cliente = 'perez' )%"

Pues que mal has entendido el uso de LIKE, te explico un poco. El LIKE se usa para hacer consultas con carácteres comodines de manera sencilla, por ejemplo si yo coloco:

SELECT * FROM tabla WHERE nombre LIKE 'A%'

Estoy buscando todos los reqistros cuyo campo nombre comienze con A, el carácter % representa cualquier combinación de carácteres. Esa es la forma de usarse. Espero te hayas dado cuenta de tu error y reformules tu sentencia SQL.