I'm not entirely sure this is a bug, but I think it is 
surprising:

Python 2.3a1 (#38, Dec 31 2002, 17:53:59) [MSC 
v.1200 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more 
information.
>>> class A(object):
...     pass
...
>>> class B(object):
...     pass
...
>>> B.__bases__ = (A,)
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
TypeError: __bases__ assignment: 'A' deallocator differs 
from 'object'

It seems like you should be able to change the 
__bases__ of a new-style class (implemented in 
Python) which inherits directly from object to another 
new-style class.  (Will the deallocator issue ever come 
into play if the only types involved are HEAPTYPES and 
object as the ultimate base?)