Hey there,
For about a week I really struggled with I2C using my ArduinoMega and the NXT, trying to get them to work. It turns out that the ArduinoMega has 10K pull-ups on both SDA and SCL, which the other Arduinos do not. The 10K pull-ups mess with the 82K pull-ups that the NXT requires on the SDA and SCL lines. You can read more about it in an article I wrote about it on my blog: [LINK]. I hope it helps others.
Regards,
Xander