Be careful that you didn't get any extra compount between the pins of the chip, and also that you didn't scratch or wreck anything with the screwdriver you used to pop the heatsink off. Look for obvious damage first, such as scratches, gouges, and burn marks. After that, I really can't suggest anything, except for maybe sucking it up and buying a Geforce MX.
edit:
WHen you took it from the freezer, how long did you wait before you tried to use it? By freezing the board, frost could accumulate in places you don't even want to think about having wet. Blast it with a hair drier, or better yet, leave it at room temperature for a day or two, then try it again.