Hello Electronics lab forum. This is my first post.
I think, you must use ATmega64, as a minimum. AT command and NMEA protocol processing requires a lot of RAM and flash memory.
For example, you can download complete Tracker project (based on ATmega128) from sourceforge...