The trick to running an investigation-based game, I think, is to not make the investigation itself the hard part. The Dresden Files game I'm playing in is a bit guilty of this. In that game, a lot of the challenge comes from trying to figure out what's going on. We investigate clues, and we might get information from them, but that information rarely suggests a clear next step. One of the players has (a couple times) just asked the GM if she could roll her Investigation ability to try and figure out what to do next. This isn't ideal.
How could this be better? New information should usually have an obvious next step attached to it. It doesn't have to come with that information. It doesn't have to be the ideal next step - there might be far better choices available to the PCs... but as a GM, you ought to make it obvious that there are things that PCs can do to advance the plot.
The other game - the Planescape detective agency game I'm playing in - had a great example of not making the investigation the hard part. We were hired by a woman to find out if her husband was cheating on her. Here, the investigation was straightforward. We staked out his place of work and followed him. The tricky part was the decision-making. We were fairly sure that his wife wanted us to fabricate evidence that he was cheating on her (so that she could divorce him). We had to decide whether we were willing to do that (there was a lot of money involved). When we found out that he wasn't cheating on her, but was involved in some other questionable activities, we had to decide what to do with that information and whether we wanted to act on it. This (not the investigation per se) is what made the story compelling.