Your temperature is running high even for stock.
I bought the 8350 (removed the heatsink 4 times --degrading the paste application a bit-- as I struggled with installation of the retention bar) recently and my idle temp is 41 C at 30 percent fan speed (which I raised to 40+ percent for idle) or about 2227 RPMs.
This is about 5 degrees higher than my stock i7 860 and so I will soon get a new HSF and paste. I haven't run tests or put a heavy load on the CPU given my fear of inadequate thermal paste distribution. [Edit] FWIW, I"m playing Drakensang and the temps are mid 40s-50s.
I have 3 stock 120mm fans in my inexpensive Rosewill case, decent air flow and have paired the CPU with an Asus M5A97 (970 technology). That might account for some difference.
4500 RPM would be top speed, my top speed is 4354 under my current fan profile.
I think I would rule out the potential problems Miks mentioned as well as your case airflow in the remote chance you have a faulty chip and need to return it. You'll want to remedy this per your warranty terms.
I was told on good authority that the 8350 heatsink was better than most AMD F3+ chips and I believe it is. I don't overclock (and too am on a budget) such is why I didn't go aftermarket...but it's still a bit too hot for my taste.
P.S. Most gamer comments I've read seem to be quite positive about the hyper evo 212 with this CPU -- at least with the Asus mobo. I don't think water cooling is needed unless you're running under extreme conditions, which I presume you are not given you went stock.
ETA: Something quite odd to me is that the 8350, at least in my set up, seems to not be very responsive to fan speed, whether it runs at 40% or 70%. I can't wait to test it under load, but to me this doesn't seem like a good thing. It should drop 5 degrees or so, one would think. That's been my experience with Intel quad-cores, anyway. Then again, I have better case air flow and improved ambient temps then I did prior.