Това, което съм склонен да намеря, решава много неща е;
mysql_query("SET NAMES 'utf8'");
Преди да бъдат изпълнени каквито и да е заявки.
Документацията препоръчва да използвате mysql_set_charset
но често виждам тази функция да липсва.
if( function_exists('mysql_set_charset') ){
mysql_set_charset('utf8', $db_con);
}else{
mysql_query("SET NAMES 'utf8'", $db_con);
}