I don't think there's anything wrong with the pull-up value. I2C drivers mus be able to sink at least 3 mA, and the minimum of 2 kΩ is determined with that in mind: 3 mA through 2 kΩ is enough to pull a 5 V bus voltage all the way to ground.
It looks to me that the I/Os haven't been properly initialized after power-on. Are you sure the reset did its work properly? Does the AVR have an internal reset (you don't mention which type you're using, and I'm not going to read dozens of datasheets), or do you have an RC circuit on an external reset pin, or maybe a reset controller like the MAX809?
I would suggest to add some code which indicates proper reset, like for instance a LED blinking at 2 Hz. Do the initialization for the blinking immediately after the initialization of the I2C. If the LED blinks the port will be properly initialized, most likely not if the LED doesn't blink.
I2C-bus specification and user manual
Using the TWI module as I2C master, Atmel Application Note AVR315
Using the TWI module as I2C slave, Atmel Application Note AVR311 (for completeness :-))