I opened a support ticket and worked with Microsoft support on this. I wanted to provide an update in case anyone else is experiencing this problem. In my case, there were a few things that helped push notifications to work properly.
I needed to run the following commands:
Set-CsAccessEdgeConfiguration -AllowFederatedUsers $True
New-CsAllowedDomain -Identity "push.lync.com"
This seemed to be the thing that got the notifications to start working. However, the audio/video would not connect properly when the call was answered. This seemed to be because I was using a wildcard certificate on the edge server. Wildcard is supported on the Standard Edition (Front End) server. But on the Edge server, the FQDN needs to be explicitly listed in both the SN and CN. Once I requested and installed a new certificate meeting these requirements, the Audio/Video now works as well.