@illuvatar, good to see you around :). I have checked the GPU temps under LINUX, and at idle there is zero difference (44-46 C). At full load, I think the GPU sits around 55-60 C (will have to check more carefully. Go ahead and try a cooler, it cannot hurt, and if it does nothing, simply return it to BestBuy for a refund.
+1 rep, @n3tninja! The thermal paste is between the GPU and the heat pipes. The heat pipes are connected to the mobo with screws which you will have to remove. You then go to Microcenter/Bestbuy and buy a syringe of thermal grease (I hear Arctic IC Diamond is best). Spread a little on the GPU and heat-sink and spread it around. You do not want too thick a layer, but it still needs good contact. Desktop OC'ers, we could use your advice.
I agree on the best chill pad. Make sure the room is not getting too warm. The Intel CPUs cut thermal at 100 C, and the GPUs are near that. Still, prolonged 80-90 C temperatures will make the thermal grease wear out faster (which exacerbates the problem) and cause more wear and tear on the GPU itself. This in turn leads to shorter product life-span.