A faulty Uno board 
I'm very glad that you found the problem 
In #29, @Deltaflyer mentioned using A4 and A5. Did you try that ?
If A4 and A5 also fail, then you could check the board with a magnifier, perhaps there is a bad soldering.
These things sometimes happen when using cheap quality boards and sensors. Sometimes a whole batch of bad products show up at Ebay/Amazon/Aliexpress. There are also counterfeit products. The DS18B20 is often used as a temperature sensor. However, if you buy a DS18B20 at Ebay/Amazon/Aliexpress, then it is almost certain a counterfeit sensor.