Deployment fails after few seconds because deploy-pod gets timeout error

Issue

When deploying the image from newly created Deployment Config (not using Build Config and build process), the deployment process fails after a few seconds with the message:

error: update acceptor rejected pod-example-3: pods for deployment "pod-example-3" took longer than 600 seconds to become ready

However, the deployment is old only several second and not 600 seconds as in message above.