I have (more or less) the same issue since yesterday: messages USUALLY don't arrive until you open the app. I haver restarted the phone several times and one time I got the message about push notifications error. I restarted again and now it seems it is working properly, connected by WiFi. Will see if it keeps working during the day...
Windows Phone 8.1 Update + Orange 4G network in Spain.
Hope this helps.