Use Ibutton to wake MCU and fire an interrupt
The solution I ended up using was utilizing the Watch Dog Timer. Using the Arduino OneWire Library the search of a present button takes approximate less than 2 ms. Now I use the WDT to wake up my device every 250 ms to search for the button. This is not as efficient as if the MCU was woken up only then a button is present. However it is still relatively low power. 

I found great information regarding the waking the device using the WDT here: http://www.gammon.com.au/forum/?id=11497