sounds like you have an msi twin frozr card with the classic crappy tim paste application. many twin frozr users remove the cooler, clean off the thermal paste, and reapply some correctly and put the cooler back on and have temps drop 3-7c.
when you say the card is new, how new? is it still under warranty? i have heard conflicting reports about msi honoring the warranty if the stock cooler is removed. that said, dont remove the stock cooler if its going to destroy your warranty as msi has a great warranty and usually replaces things no questions asked. they cut me a check for $324 a few months back for a dying twin frozr 7950, that was about $60 more than a paid for the card 8 months earlier.