If you are still under warranty, see if you can convince Apple to replace your new video card. You can perform the swap yourself if you are confident with a screwdriver.
Contact AppleCare at 800-275-2273, or try online selfservice at http://www.apple.com/support/serviceassistant/overview.html
You can also bring the unit in to an Apple Store or AASP. If you can take a picture of the screen when it is displaying the symptoms, bring it with you to aid in proving the issue. You will need to do this with a digital camera, I don't think your will be able to do a screen shot :)