The DS18B20 shouldn't have any problem at 5V, its rated for 3.0 to 5.5V.
Perhaps the pullup isn't strong enough (4k7 is the nominal value, and I've had the working fine with 12 sensors on the same bus (short bus and 0.1uF decoupler shared between sensors).
Does the 12V supply have a lot of ripple perhaps? It needs to be above about 6.5V all the time to keep the +5V line happy.