check date and time are correct....
First post so bear with me...
I've just bought a Samsung Galaxy Y which only has Gingerbread with no authorised upgrade path to ICS and I haven't had time to learn how to upgrade through the alternative channels. I had the same problem as OP but realise that it might have been fixed with later versions of the app or Android itself.
I went through the Google procedure "Problems syncing Gmail on Android" - I can't yet post links on this forum - and got all the way through to the last procedure, clearing the Gmail App data and restarting. After restart I noticed my date and time was wrong - I didn't have the "Automatic" date and time box ticked so my phone wasn't using network time. Just after I ticked this box and the date/time were set correctly, I heard my notification alert and my Gmail accounts had synced.
So...problem solved but not sure whether it was the Google procedure (although I had tried this before and it hadn't worked then) or setting the date/time to the correct values.
But if anyone is having this problem it would be worthwhile checking the phones date/time settings.