Ами сега, намерих отговора на моя проблем:
Всички колони на индекс FULLTEXT трябва да имат не само един и същи набор от знаци, но и едно и също сортиране .
Моят FULLTEXT индекс имаше utf8_unicode_ci в една от своите колони и utf8_general_ci в другите си колони.