In yet more fascinating iOS 4 news, it looks like GMail ( smtp.gmail.com ) does not have valid security certificate, per the iPhone update. You may be presented with the above message.
It does not happen to everyone, which just makes it all the more odd. Since we know that GMail ( smtp.gmail.com ) is in fact a valid provider, just go ahead and select continue.
You can click details to see the reason for invalid server identity.
In addition: some people using GMail with Exchange Services, Google Sync, have reported losing contacts and calendars from the iPhones!
Some have had issues with GMail on the iOS 4 even after deleting and re adding several times. A post on a Google support forum claims they are working on a fix and will be pushing it out.