My group wanted to play a mystery/story-based game with a different flavor of the usual D&D campaign we've been playing for the past two years. We started a big mystery/political intrigue campaign using a fairly complex system ("The Enemy Within" using WFRP 4e).
This is where I would start to ask questions. When they say they wanted to play a mystery/story-based game, exactly what were they envisioning? It sounds like they were anticipating a sort of F20 Scooby-Doo - where there was an initial plot to unravel and then they went straight to confronting the obvious bad guy, where you had something more like of an extended puzzle going.
Have you checked resources like Robin's Laws of Good Gamemastering? I've found this to be very helpful in understanding why players behave in frustrating ways, even when it's a scenario they say they want.