Sounds like you were using a factory overclocked card. Since they gave you a nice new fan, just up the core and memory clock with Rivatuner. I suggest 560/750 as a safe place for the card to be, especially if you are new at overclocking.
If anything, you just got upgraded. Rejoice