We are observing a very weird behavior with our openshift cluster. As soon as the DeploymentConfig is created, the replication controller fails with message unable to create deployer pod

Describing the rc does not give any other useful information

$ oc describe rc example-1

Name:         example-1
Namespace:    example-test
Selector:     app=hello-openshift,deployment=example-1,deploymentconfig=example
Labels:       openshift.io/deployment-config.name=example
Annotations:  kubectl.kubernetes.io/desired-replicas: 3
              openshift.io/deployment-config.latest-version: 1
              openshift.io/deployment-config.name: example
              openshift.io/deployment.phase: Failed
              openshift.io/deployment.replicas: 0
              openshift.io/deployment.status-reason: unable to create deployer pod
              openshift.io/encoded-deployment-config:
                {"kind":"DeploymentConfig","apiVersion":"apps.openshift.io/v1","metadata":{"name":"example","namespace":"example-test","selfLink":"/apis/a...
Replicas:     0 current / 0 desired
Pods Status:  0 Running / 0 Waiting / 0 Succeeded / 0 Failed
Pod Template:
  Labels:       app=hello-openshift
                deployment=example-1
                deploymentconfig=example
  Annotations:  openshift.io/deployment-config.latest-version: 1
                openshift.io/deployment-config.name: example
                openshift.io/deployment.name: example-1
  Containers:
   hello-openshift:
    Image:        openshift/hello-openshift
    Port:         8080/TCP
    Host Port:    0/TCP
    Environment:  <none>
    Mounts:       <none>
  Volumes:        <none>
Events:           <none>

Even events only shows just the timeout message

$ oc get events

8m7s        Normal    DeploymentCreated   deploymentconfig/example             Created new replication controller "example-1" for version 1
8m7s        Warning   RolloutTimeout      deploymentconfig/example             Rollout for "example-test/example-1" failed to create deployer pod (timeoutSeconds: 600s)

Here is the describe output of deployment config

$oc describe dc/example
Name:           example
Namespace:      example-test
Created:        5 hours ago
Labels:         <none>
Annotations:    <none>
Latest Version: 1
Selector:       app=hello-openshift
Replicas:       4
Triggers:       Config
Strategy:       Rolling
Template:
Pod Template:
  Labels:       app=hello-openshift
  Containers:
   hello-openshift:
    Image:              openshift/hello-openshift
    Port:               8080/TCP
    Host Port:          0/TCP
    Environment:        <none>
    Mounts:             <none>
  Volumes:              <none>

Deployment #1 (latest):
        Name:           example-1
        Created:        5 hours ago
        Status:         Failed
        Replicas:       0 current / 0 desired
        Selector:       app=hello-openshift,deployment=example-1,deploymentconfig=example
        Labels:         openshift.io/deployment-config.name=example
        Pods Status:    0 Running / 0 Waiting / 0 Succeeded / 0 Failed

Events: <none>

Does anyone have a pointer to debug the issue here?