Thank you Tyson. You nailed it.
For others who are having the same problem:
Inside your Google Checkout account go to Settings, then click Integration (on the left).
Under "Shopping cart post security," make sure you UNCHECK the box that says, "My company will only post digitally signed carts."
As I was researching this on my own I found that a lot of people are thrown by this. It's a rather obscure setting within Google Checkout.
I respectfully suggest that the awe-inspiring crew at E-Junkie consider adding this information to the documentation for Fat Free Cart.
All the best,
David