I believe the correct behavior is actually

Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "bar.py", line 7, in <module>
    C()
TypeError: foo.A.__new__(C) is not safe, use foo.B.__new__()

This is because A comes before B in the mro, and, indeed, constructing C with A.__new__ is unsafe. In fact, reordering A and B in the definition of C fixes everything.