Air MacにUSBで外付けのHDDを繋いだのですが、

Air Macユーティリティー上ではHDDを認識しますが、

パソコンからHDDを認識できない状態です。

これは、Mac上で動作している Air Macユーティリティーから AirMac Extreme USB HDD を認識するが、Windows からは認識しないという意味でしょうか。

Windowsにしても MacOS X にしても、「AirMac Extreme USB ハードディスクボリュームを Mac OS X および Windows にマウントするには 」にマウント手順が記されています。参考にしてください。

#1で示した「AirMac Extreme USB ハードディスクボリュームを Mac OS X および Windows にマウントするには」の3つの方法のいずれを用いても、Windows PC から接続できないということでしょうか？

Windowsの種類は何ですか？

少し前までZドライブで認識していましたが、スピードが遅いことからUSB接続に切り替えました。

ただ、やはり不便なのでもう一度Air Mac Extremに接続したのですが、Zドライブが表示されなくなってしまいました。

Windows PC に USB 接続で使っていた時に再フォーマットしませんでしたか？　その時のフォーマット形式は何でしたか？

AirMac Extremeは、ブロックサイズが 512 バイトで Mac OS 拡張 (HFS-plus)、FAT16、または FAT32 としてフォーマットされている USB 記憶装置のみサポートしています。これ以外のフォーマット形式でしたら、再フォーマットしてください。

参考サイト

• AirMac Extreme (802.11n): USB 記憶装置がサポートするフォーマットとプロトコル （Apple公式）

接続しているHDDのファイルフォーマットは何をお使いですか？

いわゆる「Mac OS 拡張」だと Windows 系の環境からは見えないかもしれません。

FAT16、FAT32、NTFS などでフォーマットされた HDD で試されてみてはいかがでしょうか？

（現在の状況が既にそうであればすみません）