I am having the same issue. I've managed to get both Pushover and Pushsafer to work but prefer Prowl. Especially since I have numerous notifies setup already.
I'm wondering what router everyone with a problem is using? I'm using a Unifi UDM.
I have also emailed Prowl support and am waiting to hear back. Will let you know what their response is.