It might be time to take everything apart as they said and try just the probes. Rehook the probes up and download the Arduino IDE here
http://arduino.cc/en/Main/Software.
Hook your probes(One at a time) up to Digital Pin 10(not Analog 4)
Then plug in your arduino to that PC, and it should get detected and installed.
Then open the Arduino software up and goto File->Examples->OneWire->DS18x20 Temperature
Under Tools->Board select the Arduino Uno, and under Tools->Serial Port it should already show COM1 or whatever serial port it is using for the Uno connected to your PC. If Serial Port is greyed out, it didnt detect your Uno properly, try rebooting.
If all thats right, there is an Upload button, click it and allow the script to upload. Under tools, select Serial monitor...it should start spamming values to the window. If your getting the same value over and over or no value at all your probes may be bad. If the sensors are just wired wrong sometimes they will spam out 0C or -185F ive found.
Others have been getting bad sensors, and apparently a bad sensor can screw up the entire OneWire bus, so test them one at a time to see if one of them is good and one is bad possibly.