Unfortunately, I have almost no practical experience with PIDs. I've a decent understanding of how they work, and if I were about 10 years younger, I could probably analyze the system and suggest good P, I, and D values for you. For a class project, I once designed a built a controller to cause water from a faucet to follow a certain temperature profile (80 degrees for 10 seconds, 72 for 8 seconds, 95 for 4 seconds, etc) by controlling the hot water valve. If I recall correctly, though, even after doing all the system modelling and getting good numbers to run with, it was understood that you'd still need to tweak things.
When you do the autotune, does it output (or can you assertain) the values for P, I, and D? Recall from what I wrote elsewhere, that P moves you towards your target relative to how far you are from it (faster for further away, really slow or non-existent motion when close), I keeps track of how long and far you are and adds up the product of those two to move you closer, and D watches how fast things are changing to try to reduce overshoot.
Depending on how you have the system set up, it seems to me that you would only need P to heat things. There's no such thing as thermal inertia--you can't overshoot with temperature...I was about to go into a long explanation of this, but decided I'd better wait to see if anyone actually wants to hear about it. Since you said you are overshooting, it means either the element you are using (are you using an element to heat?) has a good deal of excess energy once the desired temperature is reached, or the I value is high enough to cause continued energy contribution even after the temperature is reached.
I think I'd be inclined to play with the controller--set everything to 0, then turn P up a little and watch what happens. Does it ever get to the desired temperature, or is it always a little cooler than it should be? If it gets there, is it fast enough? If it's not fast enough, turn up P. If it never gets there, add some I. If it gets there fast enough, but overshoots, turn down P and add some I (you could try D, but i'm not sure how it will work in a thermal system...). Etc.