I'm not sure why you're having the problem, I would double check that you didn't wire the IC backwards, pins 1, 2, and 3 from left to right applies when the flat side of the probe is sticking up like in the picture I posted.
I would try wiring a single probe and resistor like my picture had done and see if it works then if you haven't.
Here's a picture of just plugging my probes in and testing it out. You can see the two probes on the right of the breadboard. They are pretty ugly as is, but water tight. They are in rigid 1/4" tubing which I got the LFS. I don't know what it's normally used for, but it was next to the 1/16" tubing that is commonly used for undergravel filters and air stones. I just wired my probe and resistor up, with the 3 wires coming out, I plugged the tubes with aquarium epoxy putty. They should work fine for water temperature monitoring, they take longer to update compared to exposed probes, but that obviously is not an option. After a few minutes they air temperature inside the tube equalizes with the outside temperature though and they seem accurate compared to my IR temperature laser and aquarium temperature probes.
I'm using the "Multiple" example in the dallas temperature probe library, I haven't modified the code at all, the data wire is connected to port 3 as the code indicates, and +5v and ground respectively.
Here's hacktronics intructions on the probe, you are right that you could just use roughly 5kohm resistors, it apparently doesn't matter.
