The best way to respond to problem-solving questions in interviews (and anywhere else for that matter) is to know what you're doing. There is no technique to fake your way thru something like this. That is of course why these questions are asked. You failed not because you didn't have some magic technique or the other guy gamed the system, but because he was better than you. If you can't solve problems efficiently in a interview, you're also not going to solve problems efficiently when confronted with them on the job. It seems they rejected you for the right reasons.
You are therefore asking the wrong question. Your issue is not with problem solving during technical interviews, but just with problem solving. This is not the place to discuss problem solving methods, so I'll only be brief. Basically, problem solving comes down to understanding the subject matter and logical thinking. You can sit down and learn more of the former, but I'm not sure how well you can learn to do the latter. The biggest mistake people seem to make when confronted with a problem statement is to assume facts not presented, and then just flail around guessing at possible solutions instead of thinking carefully about what they know, what needs to get done, and how to proceed towards that goal. If the problem is diagnosing a failure, then you design a set of experiments that break the system down into two or more parts and tell you which parts the fault is not in.
Added in response to comments
Someone objected that problem solving in a interview is different from problem solving in the real world. That is the wrong way to look at it, and I reject that notion. Real problems during the real job don't come at convient times either. You often have the boss, sales, upper management, and/or customers breathing down your neck. Answers are rarely out there where you can google them. Stuff happens, sometimes right after you've come back from a week overseas and are jet-lagged.
Also, if you're stressed out in a interview, that's totally your fault. Stress can only ultimately come from you internally. At best the external world can create demands, not stress. The kind of person you want to hire won't get stressed out, they'll take it as a challenge instead. You don't want to hire the person that can only function when everything is just right. Deliberately creating a bunch of demands during the interview is one way of weeding out people like that.
I have interviewed enough engineers to have seen a clear difference to how people react to deliberately contrived tough problems. The good ones actually enjoy the challenge and dig in. These people know their stuff and know they know their stuff, so they don't get stressed out. Again, stress comes from inside. It's those that don't know their stuff and have low confidence that get stressed out and then usually screw up as a result.
Some people may know their stuff, but just react badly to being put on the spot. However, do you really want to hire someone like that? Perhaps in a sufficiently large organization you can create a peaceful niche for someone like that and thereby utilize them effectively. However, in a small company that kind of person wouldn't be able to function when the inevitable stuff happens.
That all said, one thing you should NOT do as a interviewer is to make the candidate feel stupid and unrespected. That's because in the real job you wouldn't do that either. If you really felt that way about someone, you'd ditch them. People that work for you have to feel that they have your support and respect, and they will perform better because of it. So be positive and supportive in the interview when you're giving them a hard problem. As I said before, the good ones will dig in and actually enjoy the challenge. The losers will get flustered and hang themselves without you having to help it along. I've done this a bunch of times and can tell you from experience the difference is quite clear.
Usually a candidate gets stressed in a interview not due to a hard problem, but because they realize they are getting caught having over-represented themselves. The hard problem is only the vehicle which exposes the fraud.
Someone also objected to contrived questions in a interview as being a good test of a candidate's knowledge, and that such knowledge can only be assessed after much longer term observation on the job. There is some truth to this, but it completely misses the point. What are you supposed to do, hire ever candidate for a month then blow off the ones that don't perform? Like it or not, a interview is a 30-45 minute window where you get to asses a candidate. And yes, you can get a good feel for someone's technical abilities in that time. Asking a few contrived problems is just one of the things you do during that time.
I interview mostly electrical engineers and have also interviewed for electrical engineering positions. As a candidate, I enjoy the interviews best, and walk away with a more positive impression of the company, when at least one interviewer gives me a technical grilling. I know my stuff, so to me such questions are fun. However, more importantly, such questions give me a chance to demonstrate that I know my stuff. It gives me a good feeling I'll be working with other people that know their stuff because if they didn't, they wouldn't have made it thru the interview process. When I don't get a technical grilling, I'm always worried what kind of bozos I would be working with. Remember that interviews are two-way. I have turned down job offers when I didn't feel the interviews let me show what I can do relative to the average zombie interviewing for the same position.