ओह, तो मुझे अपनी समस्या का उत्तर मिल गया है:
FULLTEXT अनुक्रमणिका के सभी स्तंभों में न केवल समान वर्ण सेट होना चाहिए, बल्कि समान संयोजन भी होना चाहिए ।
मेरे FULLTEXT इंडेक्स में इसके एक कॉलम पर utf8_unicode_ci था, और इसके अन्य कॉलम में utf8_general_ci था।