75C is very high.

I had a Palomino-core 2000+, one of the hotter running of the range, and it 
only got to like 60C.

Some mainboards can read the thermal diode and report the temperature inside 
the core, while some read a thermistor below the socket, the difference can be 
significant, so a "75c" figure could well mean over 90c in the core, and I 
think those chips are rated to 90c only.  I know by the mid 60s, an old Athlon 
1200 I had started acting very erratic.

What sort of heatsink is it?  (all-aluminium or any copper parts?  How big is 
the fan?  How big is the heatsink itself?  Is the fan a fast-turning one?  
(60mm fans tend to go as high as like 5000-7000 rpm, but some heatsinks have 
slower ones (like 3000 rpm), 2000-2500 is typical for an 80mm).

I'd highly suspect the cooling system; there are many decent and nice Socket 
A sinks under $20.  I'd reccomend getting one with an 80mm fan, cos they'll 
give less noise for a given performance.