Hoppsan, så jag har hittat svaret på mitt problem:
Alla kolumner i ett FULLTEXT-index måste inte bara ha samma teckenuppsättning utan också samma sortering .
Mitt FULLTEXT-index hade utf8_unicode_ci i en av kolumnerna och utf8_general_ci i de andra kolumnerna.