自己レスです。
原因がわかりました。
ページの構成をフレーム式にしたのが原因でした。
CGI単体でブラウザに表示させた時にはきちんと動作するのですが、
フレーム分割したページで一方のフレームにBBSなどの
CGIスクリプトを表示させると、クッキーを生成してくれないようです。
う〜ん、この現象って僕が知らなかっただけで、
どんな鯖でも起こる、クッキーの仕様なんでしょうか・・・。