Two Way SSL Error - 400 The SSL certificate error just for client certificate

Finally, I have pinned down the root cause of the problem. There were two problems with my setup.

a) For two-way SSL, the certificate signed by the Intermediate CA must have clientAuth in extendedKeyUsage (Thanks to @dave_thompson_085) which can be verified by the below command

$ openssl x509 -in /path/to/client/cert -noout -purpose | grep 'SSL client :'
SSL client : Yes

b) Another, thing which was missing was ssl_verify_depth parameter in the nginx config file which must be 2 or more. It does not make much sense to make the number bigger than 2 in my case, but it works with any number other than 1 (which is default value). Interestingly, this is not required in nginx v1.12.X (my colleague with the exact same setup didn't have to specify this). However, it didn't work for me (nginx v1.13.5) until I used this parameter.

I can have a sound sleep after 3 days of headbanging.

TIP: Don't depend on curl much to troubleshoot two-way SSL issues, try openssl s_client instead. curl can give misleading results sometimes, see this. I too fumbled around for a while in my Ubuntu 16.04 docker container.