With the current query you are looking for a full word match. So for instance to get the row you show inserted above, you would need to do:
SELECT *
FROM parentregionlist
WHERE MATCH(regionnamelong)
AGAINST ('Birmingham (and vicinity), England, United Kingdom' IN BOOLEAN MODE);
However if you want to search for all results that start with 'Birm' you will need to add the '*' modifier:
SELECT *
FROM parentregionlist
WHERE MATCH(regionnamelong)
AGAINST ('Birm*' IN BOOLEAN MODE);
Alternatively you could also use LIKE:
SELECT *
FROM parentregionlist
WHERE regionnamelong LIKE 'Birm%';
The MySQL docs give good MATCH examples to work from: http://dev.mysql.com/doc/refman/5.5/en/fulltext-boolean.html