Get a different probe. This PTC just doesn't change fast enough with the temperature - most NTC probes change much faster, and have more like 5-10 ADC points per °C around the midpoint.
That failing, you could try to amplify the signal: you could use say an OpAmp configured to say 5x amplification, PTC signal on the positive input, a fixed voltage divider (set to produce a voltage that's at or below the lowest voltage your PTC divider ever gets) on the negative pin, like this:
