During peak current (when searching for satellites) I won't be writing any data to the SD Card.
Really? How will you control this? There isn't, typically, a "search for satellites" command that you send to the GPS. It searches for them when it feels the need, and it isn't going to tell you when it feels the need.
I was thinking that I could put the Mega328 to sleep until it starts to receive the NMEA data through the UART.
The arrival of serial data does not, normally, wake a sleeping Arduino.
Sleeping the Arduino, which uses very little power, while the GPS is sucking up power like there's no tomorrow seems a bit silly.
I was hoping to run the whole thing off of a 3.7V LiPo battery and this 3.3v switching regulator which can handle up to 300 mA.
The 329-based Arduinos are typically 5.0V devices, unless you clock them at half speed - not a beginner project. Is the GPS a 3.3V device or a 5V device? Most are 5V devices.