Error after applying SQL Server 2008 R2 Upgrade 10.50.6542 (Latest Build)
Finally! after 3 days of trying everything under the sun I found the root cause of my problem. 

The aha! moment was when I got together with a group trying to understand why this patch was deploying just fine in other servers while not in this particular one. 

We noticed that something different (among other things... that we listed in a neatly organized notepad) was that this SQL Server 2008 R2 was configured for encryption in transit (a.k.a. SSL encryption) via certificates and some settings on SQL Server Configuration manager namely:


On the Protocols for [Instance_Name] and then Properties (certificates tab)
we had select the certificate we have created for the purpose of encrypted communications.
On that same window (flags tab) we set ForceEncryption option for the Database Engine to Yes


So we started to think... what if the problem is the certificate itself?. Then we went ahead and remove the encryption configuration (the patch for SQL Server Build 10.50.6542 still applied) and the connection started working, confirming that the combination of the patching plus our SSL configuration was bonkers.

After more investigation and via a process of elimination, we narrowed down the problem to the certificates we were using. The certificate was created back then with makecert (to create a self signed certificate) and was NOT using the -a parameter. This parameter tells makecert what Hash algorithm to use. If not provided, makecert will use the default MD5 signature hash algorithm which is not compatible with TLS 1.2.

Also on the TLS 1.2 RFC you can see that explicitly…

MD5
  MD5 [MD5] is a hashing function that converts an arbitrarily long
  data stream into a hash of fixed size (16 bytes).  Due to
  significant progress in cryptanalysis, at the time of publication
  of this document, MD5 no longer can be considered a 'secure'
  hashing function.


So, in order to fix this problem, the solution is to add the -a SHA256 parameter to makecert (make sure you are using makecert version 6.3.9600.17298 and not the old one 5.1313790.0 because that one does not support SHA256 as a parameter).

I'm writing all these since the whole conundrum took me 3 days to figure out and I hope some day someone is going to be benefited from this. If only Microsoft would have included in BIG BOLD letters that MD5 is no longer supported right in the article where the patch is described!

Thanks to @Mr.Brownstone and @sepupic for all their help!