Take the NES apart right to that 72 pin connector if you haven't done it and stick the connector in the freezer overnight. A trick that usually works as when gum freezes, it's a solid block and doesn't stick at all and almost always pop out easily.

If that gum has a ninja-like deathgrip on the connector, you could try something stronger like goo-gone (do it outside, they really stink). If all else fails, get a new connector, sorry as it's likely by then the gum would have pulled some contacts out.