After upgrading iPhone 4S to iOS 6 noticed that there is no more Flag email option in Gmail account. The only option is Mark as Unread.
Gmail account was set up as Exchange rather than default IMAP account. After checking account settings I found that there is nothing in Domain field. Adding google as a domain initially seemed to have resolved the issue, as Flag option was back where it should be.
Unfortunately even though the option was there and flagging email would add a flag to the email on iPhone this was not syncing back to Gmail webmail account (Gmail calls such emails Starred).
Issue was resolved by re-adding the account as a standard IMAP account. After this flagged emails were appearing with a Star in Gmail and vice versa.
This may not be a suitable solution for everyone though. There are differences in what you can sync under IMAP and Exchange accounts.
With Exchange you can sync:
With IMAP you can sync: