I've heard about the non-budging pin problem before--never in real life, though, so it's not something I can look at... I think people may be trying to tug the pins in the wrong place. It shouldn't be difficult at all. Keep in mind that, naturally, the pins have to connect back to the main board, so there are a lot of opportunities for sticking the screwdriver in a place that won't work.
Here's my tip: When you take the top cover off the NES, stick a cartridge into the connector and observe where it makes contact. See where the bottom row of metal pins is touching (or, perhaps in this case, almost touching) the cartridge connectors? Each tiny pin has a thin, black, plastic wall separating it from the next. You need to gently wedge the screwdriver between this wall and the pin, and nudge it up.
Of course, I could be way off the mark, and your pins are made of titanium. I dunno. The important thing is to get a working NES! So, try this out right away! Congrats for your friend, AB.