Doing the autotune from cold doesn't give the best settings (even for an autotune) - the phase change can throw off the tuning.
Best way is to heat up to full liquidus then allow to cool to where you see some solidification. At that point switch the unit back on and start the tune.
I have hand tuned my parameters to minimize overshoot but still achieve a decently fast time to stable temperature. Tune by hand does take some patience.