fulltext matches failing on simple selects

[Barbie .]

We've recently upgraded to MySQL 5 ("mysql Ver 14.12 Distrib 5.0.77, for redhat-linux-gnu (i686) using readline 5.1" from mysql -V) on our live server, to the same version on our development server (same version string).

We have several gigabytes of data across several database, and to fine tuning search we have some tables specifically created to speed up fulltext searching. One of these tables is a "title" table containing the 'item_id' (foreign key into the main table), an auto incrementing 'title_id' and the 'title' field, a varchar(100). Nothing too complex.

However, the fulltext search returns all expected rows on the development server (there are approximately 510000 rows in the table, with 41 expected to match a title of "Tales from Shakespeare") for the following queries, but not on the live server:

SELECT title FROM title WHERE match(title) AGAINST ('"Tales from Shakespeare"' IN BOOLEAN MODE);
SELECT title FROM title WHERE match(title) AGAINST ('+Tales* +from* +Shakespeare*' IN BOOLEAN MODE);
SELECT title FROM title WHERE match(title) AGAINST ('+Tales* +Shakespeare*' IN BOOLEAN MODE);
SELECT title FROM title WHERE match(title) AGAINST ('+Shakespeare* +tales* +from*' IN BOOLEAN MODE);
SELECT title FROM title WHERE match(title) AGAINST ('+Shakespeare* +from* +tales*' IN BOOLEAN MODE);
SELECT title FROM title WHERE match(title) AGAINST ('+from* +Shakespeare* +tales*' IN BOOLEAN MODE);

However, the following query does work on both servers:

SELECT title FROM title WHERE match(title) AGAINST ('+Shakespeare* +tales*' IN BOOLEAN MODE);

As you might imagine this is causing a considerable amount of confusion, firstly as to why none of the first set (especially the exact match) find any results on the live server and secondly why the working query should work where the others don't.

This isn't anything to do with stopwords as the limit is 1 and wildcarded words are not excluded according to the docs on the MySQL site.

Does anyone have any suggestions for what to look for, settings that might need changing or anything that might give us a clue as to what is wrong with the searching or be able to offer a solution?

Thanks in advance.