I have an S6 edge. I had the same exact problem as the OP after migrating my info from my old S3. All notifications worked expect the Gmail ones.
I got around resetting my phone, see below:
-Open Gmail app
-Settings for app
-Select your email account
-Make sure sync Gmail is checked (mine was)
-Select days of mail to sync, change to desired setting
-Select Manage Labels *important*
Here is where mine wasn't right. Go over this list, set days to sync for what you want here (like the primary inbox, mine wasn't set to sync!)
Even doing this, it's not going to work right away - it needs time to sync up.
I suggest doing this just to make sure it does it:
-Settings in your phone
-Personal section , then select accounts
-Select Google
-Select your Gmail account
It should show Gmail syncing
-Turn Gmail sync off, then turn it back on
When it's finished syncing this time (may take awhile) - - your notifications should start working again!
Some of these steps may not be needed, but it worked for me. I made an account to share the info!
Facebook
Twitter
Instagram