I have the A64 3000+ and the MSI K8N Neo Platinum mobo, my cpu temps are 43 idle and the highest I've seen under full load has been 57. Case idles at about 44, never higher than 50 under full load. With CnQ enabled, it doesn't ever drop lower than 1.8Ghz. I don't know why though, I think it should drop more. My temp w/ CnQ is about 36/37.
I'm using the stock hsf/fan, and I have 3 80mm fans; 2 intake and one exhaust. They're the ones that came with the case (Kingwin KT-424-BK). I live in South Florida though, and it's the middle of summer, so it gets fairly hot. I need to get a thermometer for this room to measure the ambient temp... and maybe one for the inside of the case, to make sure the sensor is correct.
Also, I have a 400w Sparkle PSU. I'm thinking of switching it for an Antec TruePower 380w, mainly because it has the extra fan on it. (The Sparkle only has one fan, I think it may be a contributing factor for the high temps)