Ups, så jeg har fundet svaret på mit problem:
Alle kolonner i et FULLTEXT-indeks skal ikke kun have det samme tegnsæt, men også den samme sortering .
Mit FULLTEXT-indeks havde utf8_unicode_ci på en af dets kolonner og utf8_general_ci på dets andre kolonner.