I reproduced this bug in a test Fedora 23 environment where attempting to 
connect to one address failed (connection refused). The attached patch to Emacs 
master causes Emacs to try addresses addresses until one succeeds. Does this fix 
your problem? I suspect the code should check for error codes other than 
ECONNREFUSED, but I don't know what the list of such codes should be.