1. The first and most important step in solving nearly every game problem is talking with your players - and you probably already know this. The non-obvious part is how exactly to do it. I would probably start by asking what in your campaign players perceive as fun and what they find frustrating. This will allow you to focus on events and challenges the players are interested in and cut out what they don't like.
2. If players just aren't interested in investigation, get rid of it. Completely. Have a friendly NPC put together the clues. Have a minion betray the villain and come directly to PCs. Have the villain make an obvious move when he thinks he's ready and does not have to hide any longer. Just no more clues, no more puzzles. Cut to action.
It does not have to reduce the game to pure hack&slash. There are interesting things to do that aren't combat-oriented and aren't investigation. Present a moral dilemma. Have an NPC ask for an advice and help on business or romantic matters. Confront PCs with a culture completely alien to them. I believe you can tie any of these into the events of your campaign.
3. If player are interested in investigation or similar activities, but still get lost, you'll need some tools to help them. A few that were used in games I played and that worked very well are:
- Writing down campaign chronicle. Either the GM of one of the players writes after every session what happened, at least as a short summary, and makes it available to the whole group. Google docs or a campaign wiki work best for that. If it's a player who writes the chronicle, you should make sure that no important events are missed or confused.
- Introducing some kind of rule that allows players to pay an in-game resource to get a clear clue. "Ok, I'm paying a point for that. Of all that we heard about him during the royal ball, what is really important?"
- Allowing players to ask out of game for clarifications and encouraging them to do it. When they start analyzing the clues aloud then a) they start analyzing them, instead of sitting on them and b) you can let them know as soon as you see that they go in a completely wrong direction.
While I'm not in love with investigation personally, I like exploring various mysteries of a setting, figuring out how things really work and why. It requires a very similar mode of thinking, with gathering clues and deducing things from them. Even though I like it, I remember feeling frustrated and powerless a few times during the current campaign, while my GM was sure she gave us a lot of information. She did. It just wasn't clear what was the real information, what was just color and what was a (intentional or accidental) misinformation or omission.
She didn't skip any puzzles and didn't hand me answers. But she started asking questions - either through NPCs or out of game. And knowing what the questions are, I could start finding answers.