I'm getting the same error on CentOS (not sure which version sorry)

ssh2 is at 0.10 and libssh2 is at 0.12

I'm running libssh2 at verison 0.12 and ssh2 is at 0.10 as well.

Anyone out there that can help?

This bug has been fixed in CVS.

In case this was a documentation problem, the fix will show up at the
end of next Sunday (CET) on pecl.php.net.

In case this was a pecl.php.net website problem, the change will show
up on the website in short time.
 
Thank you for the report, and for helping us make PECL better.

This looks like it was a bug (technically, a lacking feature) in the libssh2 library rather than the PECL extension which uses it.

Please download and install libssh2-0.14 ( http://www.libssh2.org ) then rebuild PECL/ssh2 ( http://pecl.php.net/packages/ssh2 ).

I'm running libssh2 at verison 0.14 and ssh2 is at 0.10 as well. Fedora 5

php code:
$connection = ssh2_connect('192.168.13.1', 22);
if (!$connection) die('Connection failed');

result:
PHP Warning:  ssh2_connect(): Error starting up SSH connection(-5): Unable to exchange encryption keys in /root/to-nas/ssh.php on line 3
PHP Warning:  ssh2_connect(): Unable to connect to 192.168.13.1 in /root/to-nas/ssh.php on line 3
Connection failed

Using 2.6.19-gentoo-r5 and im recieving the same error 

"Warning: ssh2_connect(): Error starting up SSH connection(-5): Unable to exchange encryption keys in..."

Has this been fixed ???? Im using libssh2-0.14 and ssh2-0.10

Running libssh2-0.18 and ssh2-0.11 on SUSE 10.1 and getting the same as well: "PHP Warning:  ssh2_connect(): Error starting up SSH connection(-5): Unable to exchange encryption keys in..."

Strangely, it only happens when trying to connect to certain machines.  On others, it works great.  It would seem the issue is on the machines I'm trying to connect to but I can connect to them using OpenSSH from the command line.

I am experiencing the same exact problem.  CentOS 4.5 (Final) with libssh2-0.18 and ssh2-0.10.

The machine I'm trying to connect to uses this version of SSH: SSH-1.99-OpenSSH_2.3.0_Mikrotik_v2.9

Here is a class we wrote to solve this particular problem:

<?php

/*
	Author: Benjamin Menking <ben@infotechsc.com>
	Additional coding by David Johnson <davemann619@gmail.com>
	This code is public domain.  The author makes no warranty or guarantee of fitness or accuracy.
	The author would love to recieve changes and modifications to this code, if you are inclined to
	share.
*/
class SSH2_conn {

	const NO_PTY = false;

	private static $methods = array(
	  'kex' => 'diffie-hellman-group1-sha1',
	  'hostkey' => 'ssh-dss',
	  'client_to_server' => array(
	    'crypt' => '3des-cbc',
	    'mac' => 'hmac-md5',
	    'comp' => 'none'),
	  'server_to_client' => array(
	    'crypt' => '3des-cbc',
	    'mac' => 'hmac-md5',
	    'comp' => 'none'));

	private $ip, $name, $pass;

	function __construct($ip, $name, $pass)
	{
		$this->ip = $ip;
		$this->name = $name;
		$this->pass = $pass;
	}

	function exec($cmd)
	{
		$conn = $this->_connect();

		$stream = ssh2_exec($conn, $cmd, self::NO_PTY);
		
		if( $stream === false ) die('no stream available');

		return $stream;
	}

	function exec_print($cmd)
	{
		$conn = $this->_connect();

		$stream = ssh2_exec($conn, $cmd, self::NO_PTY);
		
		if( $stream === false ) die('no stream available');

		while( !feof($stream) )
		{
			$line = fgets($stream);
			echo $line;
		}
	
		fclose($stream);
	}

	function _connect()
	{
		$conn = ssh2_connect($this->ip, 22, self::$methods);
		
		if( $conn === false ) die("Could not connect!\n");
		
		// use this line for username/password authentication
		$test = ssh2_auth_password($conn, $this->name, $this->pass);
		
		// use this code snippet for public/private key authentication (much nicer IMHO)
		//$test = ssh2_auth_pubkey_file($conn, 'webuser',
		//	'/root/.ssh/id_dsa.pub',
		//	'/root/.ssh/id_dsa', '');
		
		if( $test === false ) die("Failed!\n");

		return $conn;
	}
}

class Router {

	private $ip, $conn;
	
	function __construct($ip, $name, $pass)
	{
		$this->ip = $ip;
		$this->conn = new SSH2_conn($ip, $name, $pass);
	}	

	function add_extern_user($user, $ip, $port, $rip, $comment)
	{
		$this->conn->exec_print("/ip firewall nat add chain=dstnat action=dst-nat to-addresses=$ip to-ports=$port dst-address=$rip comment=\"$comment\" protocol=tcp");
	}

	function add_pptp_user($name, $rip, $pass)
	{
		$ip = $this->ip;
		$this->conn->exec_print("/ppp secret add name=$name service=pptp local-address=$ip remote-address=$rip password=$pass");
	}

	function add_static_user($user, $ip)
	{
		// not needed
	}

	function verify_extern_account($name, $ip, $port, $rip, $comment)
	{
		$stream = $this->conn->exec('/ip firewall nat print');

		$str = '';

		while( !feof($stream) )
		{
			$line = fgets($stream);
			$str .= $line;
		}
		
		$comment = preg_quote($comment);

		return (preg_match("/$comment\s+chain=dstnat\s+action=dst-nat\s+to-addresses=$ip\s+to-ports=$port\s+dst-address=$rip\s+protocol=tcp/m", $str) > 0);
	}

	function verify_pptp_account($name, $rip, $pass, $comment)
	{
		$stream = $this->conn->exec('/ppp secret print terse');

		$str = '';

		while( !feof($stream) )
		{
			$line = fgets($stream);
			$str .= $line;
		}

		fclose($stream);

		$comment = preg_quote($comment);

		return (preg_match("/name=$name/m", $str) > 0);
	}

	function verify_static_account($name, $ip)
	{
		return true;
	}
}

// test unit code.  comment out to use class
$router = new Router('192.168.1.1', 'admin', '');
$router->add_pptp_user('foo', '192.168.1.250', 'bar');
$router->print_status();

?>

I had this problem when trying to connect to a server running version 1 of the ssh protocol. Upgraded the server to ssh v2 and things work nicely.