Well according to the ATI Catalyst Control Center my fan speeds were at 100%. And I can't even keep my computer on for more than 10 min before the GPU climbs up to 120 C or so and shuts the computer down. The case is cleaned out and this is the case I have: http://www.newegg.com/Product/Product.aspx?Item=N82E16811119137.
Like I said earlier, this graphics card is brand new and the same exact model as my previous one which never had overheating issues. The only problem I can think of is that I installed it incorrectly, but I don't think that is the case. I've reseated it numerous times and made sure the 2 6 pin cables to the PSU are connected correctly.