I ended up uninstalling, then re-installing Duo, and adding it back to the system again (had my admin remove my device completely and re-enroll it). Doing this fixed the issue, so obviously the OS upgrade from Android 6 to 7 somehow destroyed some hidden permission, as the app didn't seem to be able to pop up the "confirm" push notification anymore.
I have an ZTE Axon 7 that just upgraded to Android 7 Nougat and has the same issue. I initiate the VPN connection from my Windows 10 machine (worked fine last week prior to Android upgrade BTW), I get two alerts on my phone: First is the request for authentication, second is an immediate "Cannot be completed" error message previously described.
On the server side they can see me attempting but it just shows that I'm not completing authentication, so there's no actual error more that my phone isn't able to pop up the alert anymore?