Those temps are rather high. What are you using to view the temps, CPUID HWMonitor? What's the idle temp in the BIOS?
It's been my recent experience that Zalman quality just isn't what it used to be...
Have you tried using the stock HS/Fan and monitored temps with it installed? I'd start there. If the temps using it at STOCK speeds are fine, then I'd guess the Zalman is defective, somehow... Do you notice any imperfections in the contact base, heat-pipes, or fins?
When you say you applied the AS5 properly, I hope you mean you followed these instructions:
AS5 on AMD w/ large cap .PDF. Though not necessary for AS5, you can prep (or "tint") the HS base and CPU heatspreader with a small amount of paste prior to actual mounting. There are instructions for that in the AS Ceramique guide:
Go to Page 3.
If the Stock cooler works OK and you can return the Zalman, I'd do so.
Alternative Coolers:
Arctic Cooling Freezer 64 Pro
Xigmatec 1283/1284
Tuniq Tower
ZEROTherm ZEN-FZ120
Thermaltake SpinQ or CLP05xx Hydro
Scythe Mugen-2