I've had problems with overheating on my card (HD 4850). In my case it was more of a case airflow and dust issue. From the research that I did at the time, it seems like most problems with overheating tend to be physical as opposed to software related i.e: bad airflow in case, dust, poor fans etc as opposed to drivers, firmware bios etc
Try tidying the cables and cleaning dust out 1st. I guess you won't have much dust if you recently RMA'd your equipment but worth a shot. Cable arrangement dropped my temps by nearly 10 degrees and dust even more.
I suspect you may have tried these options already, in which case just ignore this.