Seems like a mounting issue. I would attempt to remove the cooler, give it a nice clean with some 70-99% alcohol, reapply some thermal paste (Mx-4 or Shin etsu if you have it), and put it back together. Should be pretty simple. The temps are obviously not normal.
I was thinking a thermal paste or mounting problem too, but if the cooler is removed to reapply paste, the warranty could be void and no RMA or exchange would be allowed.
Take it, or send it back is the best option. Whether or not to get a new or different card is up for debate.