ssh-addは環境変数SSH_AUTH_SOCKを参照し，ssh-agentと通信するのですが，ディストリビューションによってはインストール時にこの環境設定が設定されないようです．（Fedora19ではダメでした）
なので，
Could not open a connection to your authentication agent.
とエラーになってしまうことがあります．
eval $(ssh-agent)
とすることで，この環境変数を一時的に設定できます．この後，もう一度ssh-addをすれば，秘密鍵をssh-agentに登録することができます．