debería echar un vistazo a codificación utf8
¿Puede publicar qué codificación está utilizando su base de datos y su tabla? (¿Puede publicar la estructura de su base de datos?)
EDITAR:para responder a su pregunta en su comentario, la diferencia básica es que utf8_general_ci es más rápido pero no se preocupa por algunas comparaciones específicas del idioma. Puede leer más sobre esto en el enlace que envié arriba en mi publicación. De hecho, afecta el comportamiento de clasificación y búsqueda.
No importa cómo le gustaría que se comportara su base de datos, todas estas intercalaciones son útiles en diferentes entornos. En su caso, no usaría utf8_bin ya que solo compara cadenas usando sus valores binarios.
