Foreign characters behaving oddly

Hello,
I have a website that is supposed to grab a French word, and return the
English translation. The front-end has an AJAX script, that dynamically
POST's the value to the backend:

function post() {
var string = document.getElementById("string").value;
var poststr = "string=" + encodeURI( string );
makePOSTRequest('dict.eng.php', poststr);
}

Then the backend takes the script, and queries a database for 30 words most
like that word:

$query = "SELECT * FROM dictionary WHERE fr like ('" . $string . "%') ORDER
BY fr LIMIT 30";
$query = mysql_query($query);

If I enter in a word like "bonjour", the script returns the words that are
most like bonjour. A word with a special character, like "français", will
return no values, even though it is in the dictionary. The page is in
UTF-8, and the database, tables, and fields are all utf8_bin. Can anyone
please point me in the right direction?

Matt