I appreciate this is now marked as solved but for others looking at this thread I had the same issues as you did. It was only by turning off the VPN on the phone AND my provider that the email set up and downloaded straight away without any issue.
Am sharing this as for weeks I haven’t been able to get it working.