I've made a couple of PWM circuits, didnt have that problem, i think you just bought crappy rheostats. Althou almost all rheostats work with a single turn, well not even "a" turn, about 5/6 of one, and a decent one is pretty linear.
usually a multiturn one is different :
http://www.jprelec.co.uk/docs/order_...NONE&TEMP=NONE
Or with a similar design.
And another thing, the circuit on that page (Brian's circuit) uses a 10k Ohm variable resistance (R3), not a 5k, maybe thats part of the problem.