This is a quote from jims: (2nd page of 1-wire topic)
I have the grounds connected, the DQ pin on the DS18S20P connected to the pin of the Arduino, and a 4.7kohm resistor from DQ to +5v as the pullup. It is good to connect the Vdd pin of the DS18S20P to ground also so if you get a non-parasite version (DS18S20) it will also work in parasite mode.
Try to use the sensor in parasite mode. Isn't the difference between B20 and S20 described somewhere in the datasheets?