You are asking one of the most common questions asked here. This question on this processor and the cooler it comes with is obviously worries a lot of people. While that processor is technically under thermal limits it is close. Too close for my liking too. Plus it also means as the the cooler gets a little dirty there is no headroom, and heat will quickly be an issue.
IMHO the stock cooler, the stealth that comes with your CPU is just barely good enough for most 3600's but as you have received one of the chips that runs a bit hotter than the norm I would wan't something better too. This could just be luck of the draw on the cpu itself or your case has less than desirable air flow. So I would make sure that is not the case and make sure you have fans for intake and out on your case and no blocked path for the air.
Then I will tell you that an after market cooler will definitely help a lot.
I use a Cooler Master 212 evo. That gives me idle temps in the upper 30's and never over 73 degrees under load on my 3600. So cool enough that you will never throttle. This cooler is about 35 bucks in the USA.
As you have already been advised you are in safe territory right now so only you can decide what YOU are comfortable with.
