Bueno pues ya lo he solucionado, la subconsulta la converti con JOINS y funciona, aunque quizas alguien sepa una mejor forma de hacerlo.
Código:
SELECT m.id_melodia,m.titulo,i.interprete,m.id_interprete FROM melodias AS m
LEFT JOIN interpretes AS i ON m.id_interprete = i.id_interprete
LEFT JOIN bloqueo AS b ON m.id_interprete = b.id_interprete AND b.id_posicion >='$min' AND b.id_posicion <='$max'
WHERE b.id_interprete IS NULL
Saludos,