1-Wire DS18B20 on mighty 1284p can't find my sensors, same sensors work w/ Duemilanove
Turns out I had the ATMega1284p running at "just" 1 MHz. Fusing it to run at 8 MHz made everything work just fine. Stable connection, reliable recognition of sensors, no data dropouts as far as I can see.

I'll try to get in contact with the mighty1284p and Arduino OneWire Library folks to discuss this, I guess their code either hardcodedly assumes the device to be running at 8 MHz or having it run at 1 MHz makes the communication unreliable.