We have Unicode since 1991 so it is rather regrettable that such problems still keep us from doing our work. Unfortunately, the defaults are sometimes all wrong for i18n so we have to do things yourselves ...
You have done the right thing as far as HTTP is concerned, but you have to do the right thing for the MySQL connection ...
Try this:
$result = mysql_query("SET NAMES utf8; SET CHARACTER SET utf8;");
$cmd = "select * from yourtable";
$result = mysql_query($cmd); //all should data should arrive correctly encoded
To avoid having to do that in each connection you can change the .cnf file. Please have a look at the accepted answer to the following SO question: Change MySQL default character set to UTF-8 in my.cnf?
UPDATE: It turns out that the problem was indeed with the SQL connection string. However, on Apache AddDefaultCharset can also cause problems, so I leave this part of the answer.
AddDefaultCharset is nasty if you don't understand what it does! If it is set, Apache will set the charset for responses of text/html and text/plain content types. This effectively means that your will be ignored. Either set it to utf-8 as Sacx's recomments, or to off. (Incidentally if it is set not to a specific charset but to "on", this will be the same as if it was set to "iso-8859-1", which makes debugging such situations so much harder!) More info at:
http://httpd.apache.org/docs/2.2/mod/core.html
See also:
How to make MySQL handle UTF-8 properly