I initially chose a 400 watt heater for this project, and it turns out that it is far too much. The rate at which the heater heats the block is so fast that the PID controller can't shut it off fast enough. There are settings in the PID controller to allow for different rates, but this is so fast that it would be hard to regulate well. I'm going to replace the heater with a 100 or 150 watt version and that ought to make things much more stable.
Again thanks to Jeff for his insight and PID controller.
Take a look at his excellent surface mount soldering hot plate:
http://mightyohm.com/blog/2009/01/diy-pid-controlled-soldering-hotplate/