Right now it seems to be a driver problem more that a physical cooler problem. I'd wait a couple of weeks till they get the drivers running right before getting a cooler. If you need a cooler for it later the good news is that any aftermarket cooling solution that fit on the 3850/3870 will fit on the 4850/4870
People blame it on the driver, but that's just an excuse. It's still a combination of gpu that puts out more heat and lighter stock heatsink, even on the dual slot version. That heatsink is physically lighter than the stock dual slot heatsink on, say, a g92 8800gts. Not all stock dual slot coolers are equal.
It should run ok at those high temperatures, since gpu can tolerate higher temperature than cpu. But if you're still not comfortable, aftermarket cooler is the way to go.
The problem is the fan isn't spinning fast enough to keep the card cooler. I have a 4850 and was experiencing non gaming temps of 79c!! After I did the fix and set speed to 40% it's now at 55-58c normal use and stays in 60s under full load. Here's link to site to tell you how to fix.