Firstly double-check your pin-out - in fact always double-check all circuit wiring before powering up (saves
a lot of money).
Try connecting the DS18B20's 5V and GND both to GND and just use the pullup on the signal pin to 5V for power.
Don't ask me why they sometimes don't work if you connect the 5V to 5V -- I don't know.
I've used dozens of DS18B20's never the slightest issue (but mostly with very short cable).
If the sensor is on a long cable then you should (after testing without the cable):
1) used screened cable, ground connected to screen (really important)
2) do not run the cable alongside power wiring (motors, mains, etc).
3) have a 0.1uF decoupling capacitor between +5V and ground _at the sensor_
4) Have the pull-up resistor _at the Arduino end_
Don't use parasite power if you can help it, less reliable, perhaps reduce the pull-up resistor to 2k2 for very long cables...