External pull-ups with Atmel microcontrollers: what assumptions can be safely made about the impedance in tri-state mode?
When tri-stated, the pin is actually considered as an input. So look at the datasheet for the "Input Leakage Current (IIH)" (given in table 30-1, page 314). It is 1µA max. Now, look at the voltage you need for identifying the high level correctly: "Input High Voltage (VIH)", given in the same table. It is 0.6Vcc min = 2.7V (I assume a 4.5V Vcc).

So you have your maximum pull-up value: R = U/I = (Vcc-VIH)/IIH = (4.5-2.7)/1µ = 1.8 MΩ.

Another solution to help in reducing the power consumption in your situation: do not activate the pull-up all the time. Check the button state every 100ms, for example, and just activate the pull-up for a few µS before checking the pin state (you need to activate the pull-up for a small time before checking, to overcome the parasitic capacitance of the track+pin). This way, you can have very low consumption without needing external pull-up. This forces you to check regularily, however. You can't just make the MCU sleep and wait for an interrupt on the button pin. Note: during the time you're not checking (when the pull-up is not activated), you need to set the pin as an output and force it to low level (same level as if the button was pressed), otherwise, if you keep the pin as an input, its level may be undefined (nothing drives it and there is no pull-up/down). This has a dramatic effect on power consumption if the voltage settles between high and low levels (even if the inputs are schmitt-triggered).