I am facing the same issue on my Debian 7 Server. I downgraded to 1.0.1e-2+deb7u12 version of libssl1.0.0 and restarted nginx but the issue is still occurring for me. I can still see the same logs.

I also tried following these instructions(installed the deb packages made by these instructions) but even these didn't help:

apt-get update ; apt-get source libssl1.0.0
> cd openssl-1.0.1e
> dquilt pop Support-TLS_FALLBACK_SCSV
> dquilt delete Support-TLS_FALLBACK_SCSV
> dpkg-source --commit
> dpkg-buildpackage

Can anybody suggest as to what i can do to fix this?

After trying both methods, i restarted nginx by using

sudo service nginx restart

But i can still see the same error logs.

How can i be sure that nginx is picking up the updated libssl and openssl binaries? Is there any way to check if the SSL library which NGINX is using has support for TLS_FALLBACK_SCSV?