Me parece que tu código solo funcionaría si introducen dos valores y ambos campos existen en un mismo registro, de ahí que estás usando el operador AND.
En dado caso deberías cambiarlo a OR, pues la idea es no permitir que ningún valor de los dos se repita,
¡no los dos al mismo tiempo! 