I think anyone who thinks Hollings would have won in 2004 is underestimating President Bush's strength at the top of the ticket.
It also doesn't help him that Jim DeMint is a really strong candidate.
2004:
Jim DeMint (R) 51%
Fritz Hollings (D) 49%
Tenebaum didn't lose by all that much. I think Holling's incumbency would but him by 10 points or so.
Tenebaum was also about forty years younger and able to campaign more easily. While Hollings has the advantage of incumbency, Tenebaum has a major advantage of being much younger and able to keep up with DeMint on the campaign trail.
If the 2004 race had been in 2006, Tenebaum might have actually won.