I've noticed the same behavior ever since moving to 4.3 and 4.4 ROMs. But when I was on 4.2 ROMs, notifications were instantaneous.
My best example is w/ gmail. My credit card sends me an email whenever a transaction is made on my card. When I was on 4.2 ROMs the gmail notification pops up the moment I swipe my card. But when I moved to 4.3 ROMs and currently on 4.4, I'd have to turn my phone on, unlock the screen, and a few minutes later the notification would finally arrive. Some days i contemplate moving back to 4.2 ROMs cuz even my Google voice texts come in delayed as well.
I tried that app that was recommended but it didn't work for me. I still had to turn on my phone to get my gmail credit card notification. Guess my new habit of checking my phone every hour isn't going away. LoL.
Sent from my Nexus 4 using Tapatalk