ruby-1.8.7 + mysql-5.1.58 = Mysql::Error: #08S01Bad handshake

The issue:
ruby-1.8.7 (compiled from src, not rpm) can't connect to mysql-5.1.58:
"Mysql::Error: #08S01Bad handshake"

Environment:
Linux Fedora Core 12 (or 14, does not matter)
remote database server (different host) mysql-5.1.58
Ruby 1.8.7:

wget ftp://ftp.ruby-lang.org/pub/ruby/1.8/ruby-1.8.7-p352.tar.gz
tar -xzvf ruby-1.8.7-p352.tar.gz
cd ruby-1.8.7-p352
./configure && make && make install
ln -s /usr/local/bin/ruby /usr/bin/ruby

wget http://rubyforge.org/frs/download.php/74374/rubygems-1.6.0.tgz
tar xzvf rubygems-1.3.7.tgz
cd rubygems-1.3.7
ruby setup.rb

gem install rails -v=1.2.5

cd /var/www/
rails testproject
cd testproject
script/console

      ActiveRecord::Base.establish_connection(
        :adapter => "mysql",
        :host => "dbserver",
        :username => "root",
        :password => "pwd",
        :database => "test",
        :port => 3306
      )

ActiveRecord::Base.connection.select_all("SELECT NOW();")

Mysql::Error: #08S01Bad handshake
  from /usr/local/lib/ruby/gems/1.8/gems/activerecord-1.15.5/lib/
active_record/vendor/mysql.rb:523:in `read'
  from /usr/local/lib/ruby/gems/1.8/gems/activerecord-1.15.5/lib/
active_record/vendor/mysql.rb:153:in `real_connect'
  from /usr/local/lib/ruby/gems/1.8/gems/activerecord-1.15.5/lib/
active_record/connection_adapters/mysql_adapter.rb:389:in `connect'
....