So what solved it for me finally was adding resolve-prefer ipv4 to my server line.
Turns out that the frequent —
my_server changed its IP from <ipv6> to <ipv6>
log messages were causing the PORTs to clog up, and this led to the no free ports message.
This seems to be very common with folks trying to use cloudfront as a server for HAProxy, and this issue tracks it —