「プリンタが見つかりません」iPhoneからAirPrintできなくて困ってます。

プリンタ：HP Officejet 6500A Plus

無線LAN：AirMac Extreme ベースステーション

MAC：MacBook Pro

OS：MacOS 10.6.7

iPhone：iPhone 4

OS：iOS 4.3.3

iPhone：iPhone 3GS

OS：iOS 4.2.1

以上の環境で本日プリンタを購入して設置しました。

MacBookにはドライバをインストールして、

普通にWifiの接続により無線でプリントアウトできました。

しかし、iPhoneからAirPrintを試みようとしても

「プリンタが見つかりません」の表示が出てしまいプリントできません。

サポートに確認しても設定は不要との事を言われたので

プリンタの電源の入れ直し、iPhoneの再起動、復元をするように

指示を受けましたが、iPhoneの復元をする手前の状態ですが

状況は変わりません。

同じような環境、もしくはAirPrintに対応のプリンタのお持ちの方で

AirPrintが出来た方にお尋ねしたいのですが、

何か特別な設定などはしましたでしょうか？

ご教授お願い致します。

＊＊＊以下参考にしました。

AirPrintについて

http://support.apple.com/kb/HT4356?viewlocale=ja_JP

CANONやEPSONのプリンタで AirPrint を使って iPhone/iPad から印刷する方法

MacOS X 10.6.5 でなくなってしまった AirPrint のプリンタ共有機能を有効にしてくれる

ユーティリティを使って ePrint 対応でないプリンタへ印刷をする方法