Smaller value pots are probably a good idea, better exchange them for 10k
what kind of pot are you using? wirewound potmeters have a very rough (stepwise) resolution, which could also give problems.
For very smooth control better use cermet or even better plastic film potentiometers
http://www.resistorguide.com/potentiometer/

Actually using a thermistor is a good solution, they are cheap, easy to connect and available in a wide range.
The following page shows you how to connect, you need to use a lookup table to calculate the actual temperature in the arduino.
http://arduino.cc/playground/ComponentLib/Thermistor
You have to use the right lookup table for your chosen thermistor, which can be calculated using the steinhart formula:
http://www.resistorguide.com/ntc-thermistor/

I also think that strong math is just must have for electronics. At least at European universities

Hey, does anyone has an experience with CTF gaming (Capture the flag)? This is a computer security hacking wargame, sounds interesting, based on what I heard about it...