Yes - this is annoying. Using Gmail via Exchange does not star messages if you flag them, it marks them as unread. If you set up Gmail via IMAP, then you can flag/star messages, but lose the ability to push.
Here's what I do:
On your computer, go to Gmail via the web. Unders settings/inbox, add an inbox section for ALL STARRED. This will create a separate list of starred messages above your normal inbox. Any starred message, regardless of folder or label will appear here.
On your iPhone, if you get a message you want to star, move it to the "Starred" folder under [Gmail]. Technically, this moves the message out of your inbox, but thanks to your ALL STARRED section above, you'll be able to see all your starred messages anytime you log into Gmail.
Otherwise, if you don't set up the separate inbox, messages starred via the iPhone will moved out of your inbox, which in my workflow, means I never see them again.