We found the source of the problem in more detail at our workplace and solved it.
It seems that Apple (Apple/Google?) decided to change from using IMAP over SSL on port 993 for outgoing GMail to using smtps over port 465.
At our workplace we block unneeded outgoing ports. Since port 465 wasn't previously used, it was blocked - hence the problem.
We solved this problem for our iPhone users by opening outgoing port 465 to allow smtps to GMail. I had spent some time trying to switch back to IMAP over SSL through the iPhone configuration options but I didn't have any luck. The port used was apparently fixed by the protocol. Your mileage may vary.
Hope this helps others.