The only thing I can think of is to change to Manual or Fetch, for some mail through, then switch back to Push and see if it resets things.
It sounds like you're going to Settings >> Mail, Contacts, Calendars, selecting your account and changing things in Mail Folders to Push. but if you haven't, then check this too. You can select multiple folders here. So maybe deselecting the Inbox, letting it run for a while, and the selecting it again will reset something. Then again, maybe this only effects outgoing mail.
I know that Google has recently started rolling out it's Priority Inbox to all users. You could check that setting and try with it on or off. Mine is currently off.
That's all I can think of for now.