Connecting 3.3 and 5 V devices
I think you are using the wrong figures. You must use the output figures for the output, and the input figures for the input, and do that in both directions and for 0 and 1.

For the AT->GPS:


AT out maximum for 0: 0.9 V
GPS in maximum for 0: 0.8 V


Strictly speaking the AT might not pull the line low enough, but in practice (with no load on the line) this will be OK, even without a voltage divider.


AT out for 1: min 4V2, can be up to 5V
GPS in for 1: min 2V0, max Vcc (3V3)


This is a problem. A voltage divider will do fine at this low speed, don't take the values too high. I would take 1k5 / 1k, but probably 10k / 10k will do just as well.

For the GPS ->AT:


GPS out at 0: 0 .. 0.4
GPS out at 1 : 2.4 .. 2.8
AT in at 0: 0 .. 1.5V
AT in at 1: 3 .. 5.5V 


One problem here: the output level of the GPS for a 1 is not enough to be guaranteed to be seen as 1 by the AT. You can go for tricky passive solutions here, but a simple HCT gate at 5V will do the trick, their minumum input level for 1 is 2V0. Take for instance a 74HCT00 (2 gates in series), or any other non-inverting set of gates.