This has nothing to do with Python 3.  There's a difference in __str__ handling between Python 2.6 and Python 2.7.2.  It's enough to crash BeautifulSoup:

[Thread-8] Unexpected EXCEPTION while processing page "http://www.verisign.com": global name '__str__' is not defined
[Thread-8] Traceback (most recent call last):
...
[Thread-8]   File "C:\projects\sitetruth\BeautifulSoup.py", line 646, in prettify
[Thread-8]     return self.__str__(encoding, True)
[Thread-8]   File "C:\projects\sitetruth\BeautifulSoup.py", line 621, in __str__
[Thread-8]     contents = self.renderContents(encoding, prettyPrint, indentContents)
[Thread-8]   File "C:\projects\sitetruth\BeautifulSoup.py", line 656, in renderContents
[Thread-8]     text = c.__str__(encoding)
[Thread-8]   File "C:\projects\sitetruth\BeautifulSoup.py", line 415, in __str__
[Thread-8]     return "<!--%s-->" % NavigableString.__str__(self, encoding)
[Thread-8]   File "C:\projects\sitetruth\BeautifulSoup.py", line 393, in __unicode__
[Thread-8]     return __str__(self, None)
[Thread-8] NameError: global name '__str__' is not defined

The class method that's failing is simply

class NavigableString(unicode, PageElement):
...
    def __unicode__(self):
        return __str__(self, None)   #### EXCEPTION RAISED HERE ####

    def __str__(self, encoding=DEFAULT_OUTPUT_ENCODING):
        if encoding:
            return self.encode(encoding)
        else:
            return self

Using __str__ in the global namespace is probably wrong, and in a later version of BeautifulSoup, that code is changed to

    def __unicode__(self):
        return str(self).decode(DEFAULT_OUTPUT_ENCODING)

which seems to work.  However, it is a real change from 2.6 to 2.7 that breaks code.