If the box was truly cheap it's not surprising the heatsink was sub-optimal. I have been very pleased with the
TennMax cooling devices, my OpenBSD-powered I-Opener has a Lasagna fan and no other heatsink, and its uptime is in the hundreds of days now.
IIRC Athlons are not as flat as Intel processors. This implies you need more, not less, thermal paste to fill the gaps. There's a balancing act here. You want as little thermal paste as you can get away with (thermal paste, while good, isn't as good a conductor of heat as metal is, so you minimize the amount) but you want as much as you need to get contact everywhere.
The good paste is the messiest, most disgusting material ever packaged. It comes in a silver tube with a blue sticker on it (sorry, I don't have one to hand right now, so I can't tell you the mfr.) It will get everywhere and it is hard to remove from things. Wear old clothes, do not let the pets near it. Get four times as many wiping cloths (use cloth, not paper towels) as you think you could possibly use and have them ready before you ever remove the old heatsink or open the new tube of thermal paste.
Take the heatsink off and put it on one of the wiping cloths. Look at the pattern of how the old paste got smooshed out on the CPU and heatsink, see if there were any gaps or voids. If you applied the paste yourself, and you see you didn't use enough, well, use that knowledge when re-applying the new stuff.
Now try to remove as much of the old stuff as you can, unless you know it is the same as the new stuff you'll be applying (mixing oil-based things from different manufacturers can result in a sticky mess from incompatible oils).
Spread the new compound on whichever part (heatsink or CPU) you think is easier. I always put it on the heatsink. Try to smooth it out as best you can, you don't want any voids. Move everything slowly, if you go too fast, the thermal paste will sort of stick together and make thin blobs that often cover voids.
Carefully, evenly and slowly, smoosh the heatsink down onto the CPU. If you have done it just right a tiny bead of the thermal compound will ooze out all around the edge of the heatsink. If the bead is very small you can leave it alone but it is usually worth trying to remove. Flatten a thin soda straw or hollow coffee stirrer, cut the end at a 45 degree angle, push it down so it's oval, and use the cut-off point to sort of shovel the material out of the gap. If you get no bead at all, you used too little thermal paste and now you are really going to have a mess, because you'll have to separate the parts again and add more paste.
Thermal paste is a very bad solution but unfortunately every other solution is worse. There are BN-loaded rubber patches sold by Shin-Etsu that work pretty well if you have the time to design the interface and order the right thickness of material (and can afford it) but IMHO that solution is over the top for a PC.