CPU is to hot. I Think its the retail heatsink. Please Help

have a brand new amd athlon 3400 processor in my my new computer. The processor came with a retail heatsink and it said i need to use that one or the warrenty would void. So I put the processor on and put the heatsink on and everything went on right. I'm monitoring my computer and the cpu temp is at 63 C when its using 100% load. When it's not its has about 49 - 51 C temp. I ran Prime 95 for about 3 hours and the proccesor stayed at about 63 - 64 C with no errors. But now I installed cpuidel and prime runs at
59 C. So the processor is stable, it just needs to lower the temp. How can i lower the temp. I was told to remove the heatsink and get a nice one and put arcitc thermal compound on it. I think its just the retail heatsink is so crappy. It even came with a pad insted of paste. What can I do?