Well, the temperature sensor you're using is digital so that rules out A/D conversion and reference-voltage issues.
I would verify that the 18B20's supply voltage is within spec for both your supplies (3.0-5.5V). Otherwise, it's probably a software issue. Maybe if the crystal is running fast it's causing the PIC to request readings from the 18B20 faster than it's rated for.
EDIT: One more thing... is your 5V supply stable, and providing enough current? Maybe it's got ripple or sag that's affecting your circuits. Try putting a 100uF cap across the 5V supply input, and a .1uF cap across Vdd/Vss on the PIC as close to the PIC as possible.