ヒントありがとうございます。
色々試してみましたが、文字コード回りは今一つ良く分かりませんね。
みなさんのヒントとウェブ情報を参考にとりあえず次のようにしてみました。

html = urllib.urlopen(url).read()
html_coding = chardet.detect(html)['encoding'].lower()
soup = BeautifulSoup(unicode(html, html_coding, 'replace').encode('utf-8'))
text = soup......
print text.encode('euc-jp', 'replace')

単純にprintの時に text.encode('euc-jp', 'replace')とかだと、何故か全体がわけわからないコードになりました。
2.5.4でやってるんですが、3.xになるとこの辺もっとスッキリするんでしょうか。