For all those who might run into this problem some time soon...
I had set my headers to utf-8, the database, and the table (and even the column) to utf-8, yet arabic characters would display as interrogation marks. I googled for a while (as always), and found this, added after the mysql_connect() code, to fix my problem:
mysql_query("SET NAMES 'utf8'");
mysql_query('SET CHARACTER SET utf8');
cheers!