Unfortunately Google has dropped support for Anonymous Diffie Hellman ciphers needed for encrypted connections to certain servers. This is probably not a bug but intentional.
You will need to switch to SSH or to x509 certificates (if your VNC server supports it) for your security needs.
If using Linux, you can just use the AutoX functionality in bVNC:Instructions for configuring AutoXOtherwise, here are some pointers for other VNC servers out there.
For Vino (built into most Linux distributions, mostly used with GNOME ecosystem):
Run the following once on the command-line:
gsettings set org.gnome.Vino require-encryption false
For x11vnc:
Add the options to your command-line:
-ssl -vencrypt nodh:only
For TigerVNC for Linux and Windows:Either disable all secure methods (not recommended), or generate a certificate and start the server using the certificate. Please note that the instructions below are just something I threw together years ago and if you find something doesn't work for you, feel free to reply to this announcement with corrections:
1) Install OpenSSL. For Windows, get binaries here. For Linux, install it with your distribution's package management utilities.
https://wiki.openssl.org/index.php/Binaries
2) Generate key and cert:
openssl req -new -newkey rsa:2048 -days 3650 -nodes -
x509 -keyout server.pem -out server.crt
3a) For Linux, (REPLACE /path/to with actual path) when starting the server, add the following to the parameter list:
-x509key /path/to/server.pem -x509cert /path/to/server.crt
3b) For Windows, change command-line for server start link (REPLACE c:\path\to\your\ with the actual folder where you generated the files):
"C:\Program Files (x86)\TigerVNC\winvnc4.exe" -x509key c:\path\to\your\server.pem -x509cert c:\path\to\your\server.crt -noconsole
4) For Windows, if running the server as a service, you can edit the registry (thanks phantom.ololo). If you generated your key in C:\Program Files\TigerVNC\:
a) Run "regedit"
b) Add the following registry entries to HKEY_LOCAL_MACHINE\SOFTWARE\TigerVNC\WinVNC4
x509key (reg_sz), value is path to key (C:\Program Files\TigerVNC\server.pem)
and
x509cert (reg_sz), value is path to cert (C:\Program Files\TigerVNC\server.crt)
c) Reboot
For details, see that all anon ciphers have been dropped in API23 and later (Android 6.0+):
http://developer.android.com/reference/javax/net/ssl/SSLEngine.html