[The following is based on my experiences in 3.5e, but from what I know about Pathfinder it should be trivially adapted. Also, I apologize in advance for what I'm certain will be a post filled with incorrect terminology -- I've been playing 4e for quite some time now, and it's been even longer since I last sat down with 3.5e.]
If you think Diplomacy is broken at level 5, just wait until you get to the Epic levels! This is where we were when my DM decided to address it.
They way he approached it was to completely ditch the static DC list -- static DCs make sense for climbing ladders (which don't typically get harder as you get higher in level), but they don't make sense at all when you're dealing with more and more experienced and powerful individuals; just like AC and other such things, as the CR goes up so, too, must the DC.
So he sat down and took the table of Diplomacy skill DCs and turned them into situational modifiers. I think he started with "Neutral" granting a +4 (reasoning being that changing people's minds is not easy, even if they don't dislike/distrust you), and then each step toward Hostile added an additional +2, while each step toward Friendly added a -2.
The resulting modifier was then used on the NPC's own opposed Diplomacy roll. Thus the table of Diplomacy DCs that is so trivial for PCs to game was gone, replaced by opposed checks to modify a character's attitude.
But he went even further. Between each stage on the "trust continuum" (i.e. Friendly, Neutral, Hostile, etc.), the DM added a "half step"; a successful Diplomacy check would move the NPC's attitude half a step, not a full step, thus requiring 2 successes to effect a change in the character's attitude. (When an NPC is on one of these "half steps", his/her attitude is the one "rounded" toward neutral; thus an NPC is effectively Neutral across 3 distinct "steps", but 2 "steps" for all others.)
Finally, he added one more thing: Continued successful/failed checks could move an NPC further than the ends of the "attitude spectrum", although no further mechanical advantages were earned. What it did do was make it less likely for the NPC's attitude to be changed later, by simply keeping track of how many "steps" would need to be adjusted.
These were the mechanical changes he house-ruled into Diplomacy. He also required certain role-play elements to also be met before a Diplomacy check could even be attempted -- the Halfling Bard walking up to the dragon and rolling an impressive 34 Diplomacy is just wasted effort if said dragon isn't even listening! There were also common-sense limitations imposed: a dragon who's entire life is centered around accumulating his horde is not going to just give it up, no matter how many Diplomacy successes the Bard accumulates!
I've run into this problem a few times at my table. I found that the two most effective ways to retain the realism and our perception of character are either to explain it with fluff or make both player skill and character skill important.
Explain it with Fluff
You have to keep in mind that the characters in most parties most likely think in very different ways. Just because the barbarian can't understand the theories the wizard spouts off doesn't necessarily mean that he's dumb. In fact, his hard lifestyle might have made him a lot more practical at solving practical problems than the wizard who has been shut up in his study for the past who knows how many years. Similarly, even though the dwarf may only have an INT score of 8, he's spent his life working stone, he has a knowledge base that nobody else in the party does. Perhaps you can explain the characters sudden epiphany with one of these devices.
If you really know your group well, you might know their particular puzzle solving strengths. In that case, make the puzzle you intend for them to solve have a theme their character might know about. This takes a very good knowledge of your players but if you can pull it off, everyone will stay immersed and nobody will every be the wiser towards your cunning ruse.
Combining Character Talents and Player Skill
If you enjoy using mechanics more than fluff to solve this problem, consider making these riddles a partial skill challenge. While posing the question, make sure to give some fairly obvious hints that knowledge in certain skills may prove useful to finding the solution. For example, maybe a riddle has an allusion to some hero in the lore that only the bard with his expertise in history would know. Once he catches on and makes a history check, you can tell him some information from the story that makes the answer much easier to find. If you want to make it a particularly hard challenge, make it so that multiple of these hidden clues have to be discovered so that the players can figure out the puzzle.
In the end, if none of these work, it isn't a massive problem. Sure it didn't make much sense as far as characters go, but the plot is advancing and everyone will soon get into the proper mindset again. It's far worse to make a barrier to plot advancement than to see one easily overcome by the wits of your players.
Best Answer
First of all, puzzles usually don't really fit into the rules of most games. Players don't solve them by using the mechanic abilities of their characters, they are solving them by using their own deductive reasoning. That's why I would recommend you to design challenges, not puzzles. A puzzle can be a nice distraction, but if puzzle solving becomes the main activity in your game, you don't need to roll characters.
Regarding roleplaying social interactions: It is usually far more fun and far more immersive to actually roleplay how you would convince an NPC to cooperate with you than to just roll a die ("You have to abandon your evil plan for world domination because.... Ha! 20! You MUST do what I say."). But if you resolve all verbal interactions with pure roleplaying, then social skills aren't relevant, and those players who built their characters especially for these situation are punished.
There are two ways to apply social character skills in a meaningful way without preventing roleplaying dialogs:
Roll before the dialog, and make the roll impact the initial attitude of the NPC. When the player rolls bad, the NPC will be distrusting and unreasonable. When they roll good, they will be friendly and easy to convince.
This works especially good for price negotiations. When a PC wants to buy or sell something, look up the recommended price in the rulebook, and then increase or decrease it with a fixed function based on the outcome of the player's skill check. Make that the price the NPC believes the item is worth and then haggle in-character.
This doesn't work very good, though, if your game system has a wide variety of social skills. It is sometimes hard to predict in advance what skill(s) will be applicable to a conversation before you know what arguments the players are going to make.