SSH ist unable to negotiate a key exchange method after latest update when curve25519 is required

[omni-vi]

After the latest open-ssh update (6.6p1-2ubuntu2) I can't connect to my debian servers when I require KexAlgorithms curve25519-sha256 for that connection.
I'm using the homebrew Mac OS version of openssh as client and ubuntu sshd as server. It used to work up until 6.6p1-2ubuntu1

The funny thing is, the ciphers seem to match during the handshake but I get that error nevertheless.

ProblemType: Bug
DistroRelease: Ubuntu 14.04
Package: openssh-server 1:6.6p1-2ubuntu2
ProcVersionSignature: Ubuntu 3.13.0-24.47-generic 3.13.9
Uname: Linux 3.13.0-24-generic x86_64
ApportVersion: 2.14.1-0ubuntu3.2
Architecture: amd64
CurrentDesktop: KDE
Date: Sat May 24 20:35:42 2014
InstallationDate: Installed on 2012-08-25 (637 days ago)
InstallationMedia: Kubuntu 12.04.1 LTS "Precise Pangolin" - Release amd64 (20120820.1)
SourcePackage: openssh
UpgradeStatus: No upgrade log present (probably fresh install)

[Colin Watson (cjwatson)]

We needed to apply a fix to curve25519-sha256 key exchange supplied by upstream, but that involved disabling that key exchange method for unpatched 6.6 and earlier versions. OpenSSH 6.7 will fix this when it's released, but in the meantime I suggest applying the same patch to your homebrew client (and perhaps getting the package maintainer to do so as well; I'm not familiar with how homebrew works).

  https://lists.mindrot.org/pipermail/openssh-unix-dev/2014-April/032494.html