I'm on my second from EVGA, and that hasn't solved the problems. I started with the 4g over-clocked version and my PC would shut down with 20 seconds of booting (or sometimes during booting.) Put in my old card and there were no problems.
Spent 2 days doing most of the things described by the OP as well - finally decided it was the card. Took it back to Micro Center and exchanged it for the 2G EVGA non-overclocked model.
Exact same problems.
Although possible, I doubt I got 2 bum cards in a row - but I can't for the life of me figure out the problem on this. For now, going to have to stick with my old ATI Radeon HD 5850.