There has been little research on task complexity and difficulty in music information retrieval (MIR), whereas many studies in the text retrieval domain have found that task complexity and difficulty have significant effects on user effectiveness. This study aimed to bridge the gap by exploring i) the relationship between task complexity and difficulty; ii) factors affecting task difficulty; and iii) the relationship between task difficulty, task complexity, and user search behaviors in MIR. An empirical user experiment was conducted with 51 participants and a novel MIR system. The participants searched for 6 topics across 3 complexity levels. The results revealed that i) perceived task difficulty in music search is influenced by task complexity, user background, system affordances, and task uncertainty and enjoyability; and ii) perceived task difficulty in MIR is significantly correlated with effectiveness metrics such as the number of songs found, number of clicks, and task completion time. The findings have implications for the design of music search tasks (in research) or use cases (in system development) as well as future MIR systems that can detect task difficulty based on user effectiveness metrics.