Check that the previous video card's software was uninstalled from Add/Remove Programs, and the card was removed from Device Manager.
Next, try different drivers from the CD that came with the card, and from ATI.
If no luck, then reseat the card making sure that it's fully seated. Sometimes a healthy push is needed to do this.
If that's ok, then make sure its cooling fan is running, and its heatsink is securely mounted and correctly positioned so there are no air gaps between the bottom of the heatsink and the card's chipset.
If ok, then remove the computer's cover, and run an external fan blowing on the video card.
If that works, then your system needs more cooling fans.
If an external fan does not help, then see if the card works on another system.
If the same problem happens on another system, then the card may be defective.
If it works ok on another system, then the power supply on your system may be getting overloaded due the higher power demand from the video card.
What is your power supply's watt capacity, and how many drives, PCI cards, external USB and/or firewire devices, and fans are installed on your system?