I think my issue what binding Consul to docker0 while Docker is starting. Half the time the interface wasn't ready. I don't remember exactly how I fixed it but with SystemD you can just specify a dependency.