It was a database corruption issue.
If this happens again - you could try this:
- Long press on the account -> options and folders -> folders
- Wait 10-30 seconds for the app to refresh the folder list
- Find [Gmail] and under it Sent ("Sent Items", "Sent Messages", I forget the exact name and it can vary too)
- Tap the name, and choose "Sync with Sent".
- You may also want to check Trash / Bin (Sync with Deleted) and Drafts and Spam. You could also set [Gmail]/All Mail to "Archive don't sync" (recommended option for this "very special" Gmail folder).