that's all been figured out here already
ok, that's great, and if the boost regulator gets you the time you need then you're of to the races(ok, the forest).
what i was getting at is that, if you need to squeeze hours out you might be able to run the whole thing on 3 aas with no regulator at all. Don't know about the gps but some avr's are fine down to 3v.
Note that there are a few un-minty boost regulator kits that will work just as well and deliver in the 100ma range. The Pololu 798 5v boost regulator delivers 5v up to 100ma from anywhere from 1-4 AA's and cost me $5.75.