Thanks for the info. I don't know a lot about the internals of how the PID algorithm works - but i'll have a fiddle with it. There is a PID auto-tune library for Arduino:
http://playground.arduino.cc/Code/PIDAutotuneLibrary
I'm not sure what method it uses though.