The sensor is correctly wired to the Arduino: VCC to 5V, GND to GND and DG to pin 10 (and I tried Analog 0 too with same results)
Not quite sorry...
pwillard has it:
a 4.7k pull-up resistor must be connected to the 1-wire bus.
Although the arduino playground page implies you only need the 4.7k resistor in parasite mode (which you are not using), it needs to be there in the direct-power mode too.
I ran into this same problem after updating my Arduino dev environment from 0010 to 0016. The onewire sample program ran in the 0010 version, but generated crc errors in 0016.
To fix the problem, I deleted onewire.o from the 0016 hardware/libraries/onewire directory, then restarted the arduino dev environment. That forces a recompile of the .ccp file which creates a new object file that works in 0016. Hope this helps.