... I suspect the fix will be pretty straight forward (call tp_str and if the result is 'unicode' the produce a 'unicode' string). Again, is there some reason why we don't want this behavior?
Yes: '%s' is documented as "String (converts any python object using str())". It's str(A()) that raises the exception you're seeing, not interpolation. To worm around that, you'll effectively have to duplicate PyObject_Str's implementation (which is more than just calling tp_str -- that may not exist -- you'll end up at least duplicating PyObject_Repr's implementation too) inside PyString_Format(), and end up with a mess that's harder to explain too.
The *real* problem (IMO) is that we don't have a format code that means "stick the unicode representation here", i.e. there's no format code that triggers PyObject_Unicode() directly. unicode.__mod__ treats '%s' that way, but that isn't documented.