Full text BOOLEAN MODE queries seemed to stop working, the same query against the same records stopped returning any results.
It seems that changing the data structure of the tables affected the fulltext indexing in an odd way - the changes added new columns that weren't fulltext indexed or anything and so shouldn't have even required index regeneration.
My first approach was to rebuild the tables with the new data structure. This didn't fix it.
The next thing I tried was rewriting the SQL Query, eventually I added a match() against() > 0 condition and suddenly everything worked again. It seems the match/against condition was returning a non-true value when boolean mode was used but was greater than 0. Very very odd.