Sorry for the noise here.
I am not sure if I got to the bottom of the problem but I was able to “unblock” myself by removing the ~/.fly/config.yml which seemed to have some Wireguard information.
My uninformed guess I removed those peers using the CLI at some point so they were stale. So when I ran a fly deploy the next time, it created a new connection that was valid and the deploy went fine.
Hope this helps further debugging and other people running into this issue.