Power supply for a 3.3v portable device based on dsPIC33FJ128GP804
One way to get better battery life would be to go with an intelligent switching regulator which can transition from buck mode (step-down) to boost-mode (step-up) as the batteries discharge. This allows you to more deeply discharge the batteries vs. a linear regulator solution. Linear Tech and Texas Instruments offer parts that provide this functionality, among others.