I think this is fundamentally due to the problem identified at step 4 where the pod and service IP ranges overlap.
That is addressed by bug https://bugzilla.redhat.com/show_bug.cgi?id=1473858
Once that issue is addressed we can work out if there are other problems or if that is the root cause of everything.
*** Bug 1491394 has been marked as a duplicate of this bug. ***
The MTU was not set correctly for the interface (based on the underlying OpenStack networking configuration).
This was messing the etcd traffic up and making all sorts of things misbehave.