Vistaで確認しました。
受け入れ側の設定
[リモートデスクトップアクセスを許可します]
コントロール パネル→システムとメンテナンス→システム→システムの詳細設定→システムのプロパティ→
リモート→リモートデスクトップ
下記のいづれかをセキュリティレベルにより選択します。
[リモート デスクトップを実行しているコンピュータからの接続を許可する]
接続元のWindows Versionが不明である場合にはこちらを選択します。
[ネットワーク レベル認証でリモート デスクトップを実行しているコンピュータからのみ接続を許可する]
接続元がVistaであることが分かっている場合にはこちらを選択します。
[ファイアウォールを許可します]
あまりお勧めはできませんが、セキュリティが安全であることが確認できていればファイアウォールの設定を無効にします。リモートデスクトップの設定がサーバー側、クライアント側両方とも正しく設定されているにもかかわらず、接続できない場合には一時的に無効に設定します。
コントロールパネル→Windows ファイアウォール→設定変更→Windows ファイアウォールの設定→全般
"無効"を選択します。
Windows ファイアウォールの設定→詳細の設定
ネットワーク接続の設定→チェックボックスをすべて外します。
クライアント側の設定
[ファイアウォールを許可します]
受け入れ側の設定→[ファイアウォールを許可します]を参考にしてください。