No encuentra nada porque ningún registro cumple con la condición que exiges, que su ID_interes sea a la vez 3, 4, 5: eso es lo que le estás pidiendo con tu consulta.
Para lo que quieres, tendrás que hacer una subconsulta parecida a esta, que te trae todos los datos de usuarios del usuario o usuarios que cumplen esas condiciones.
Código:
SELECT * from usuarios where ID_usuario IN (SELECT u.ID_usuario FROM usuarios u INNER JOIN interesado i ON u.ID_usuario = i.ID_usuario_interes WHERE u.ID_pais = 46 AND u.genero = 1 AND ID_usuario IN (select i.ID_usuario_interes from interesado i where i.ID_interes = 3) And ID_usuario IN (select i.ID_usuario_interes from interesado i where i.ID_interes = 4) and ID_usuario IN (select i.ID_usuario_interes from interesado i where i.ID_interes = 5))