The PHP documentation has an example that provides the 3rd argument. The author of this post http://phing.tigris.org/ds/viewMessage.do?dsForumId=1083&viewType=browseAll&dsMessageId=3022056#messagefocus (Derek Gallo) had the exact same issue, and he was able to point me in the right direction. Thanks Derek. It seems that some distributions require the extra parameters. In the end, I converted my code to use phpseclib as it is a pure PHP solution that doesn't require any special modules.
$methods = array(
'kex' => 'diffie-hellman-group1-sha1',
'client_to_server' => array(
'crypt' => '3des-cbc',
'comp' => 'none'),
'server_to_client' => array(
'crypt' => 'aes256-cbc,aes192-cbc,aes128-cbc',
'comp' => 'none'));
ssh2_connect("myhost", 22, $methods);