Primero las gracias, segundo tal como tenia planteado el problema parecía ser de mysql, ahora gracias a tu respuesta veo que el asunto era con Php.
Pero acá lo relevante es agradecer tu valiosa ayuda, gracias a la nueva estrategia pude construir mi consulta y funciona así:
Código PHP:
$provincia = $_POST['provincia']
$where = "where";
if($provincia!="Todas las provincias")
$where= "WHERE provincia ='$provincia' AND";
$result = mysql_query("SELECT * FROM mi_tabla $where tipo='$tipo'
AND destino='$destino' ");
