You could always try a hybrid murder mystery.
With the game I am currently making, I realized I loved mystery games(I've beaten every Phoenix Wright game and both Professor Layton games), but I also love traditional RPGs. So I wove it all so the mystery guides you into battles and such. The mystery itself introduces gameplay mechanics that work for the traditional RPG parts.
But that's also because puzzle games aren't the sort of thing I want to make. If you think you can make enough interesting and fitting puzzles to stall out the story, go for it!
You need a strong cast of characters and lots of plot twists to pull it off. I had a hell of a lot of fun tangling my story, fixing up plot holes, making characters and working them into the mess, adding layers and layers and layers. Just remember though - at the end, explain the crime step by step so that the player/reader can see how it all fits together. If you have a bad ending, the player will forget all the fun they had getting there. (I was fairly disappointed with the ending to the 2nd Prof. Layton for instance, as it was a little bit obvious, a big cop-out and not very logical.)