It will work if 'A' subclasses from 'unicode' but should not be necessary, IMHO. Any reason why this shouldn't be fixed?
Check the recent python-dev archives for a long and nauseating thread about interactions between __str__ and unicode.
Although that really doesn't answer this particular question. It was about str() and its interaction with __str__ and __unicode__, and whether Python should support __unicode__.
For the specific issue, I would maintain that str() should always return string objects. I'm not so sure about %s since, as Neil observes, '%s' % unicode_string gives a unicode result. I can't see any harm by supporting this operation also if __str__ returns a Unicode object.