Couple of thoughts - Crunch, are you sure that you are rebuilding the OneWire object every time, and not just reusing the previous object file? Make sure you delete the OneWire.o file before clicking verify.
Also, I tried using a 47K resistor on mine, it wouldn't work at all like that. I've found that 1K is about right.
And finally, I found that periodic interrupts play havoc with the search function. If you are using a periodic ISR, try executing a noInterrupts() call just before calling the search to turn off interrupts, and then execute an interrupts() call afterwards to turn them back on.