I came up with a fairly simple way to overload isinstance() and issubclass().  The class that is the second argument can define a (class) method named __instancecheck__ or __subclasscheck__ which, if present, will be called *instead* of the normal approach.

The names are different to remind users that the calling convention is the opposite -- isinstance(x, C) maps to C.__instancecheck__(x).

Oops, forget the first attempt; isinstance(Integer(), Integer) would be False!  Now it's True, and more tests are added.
File Added: typechecks.diff

I'll add a description and motivation for this to PEP 3119.

Version 3 compiles with older C89 compilers like gcc 2.96.
File Added: typechecks.diff

FWIW, this can run into unchecked infinite recursion easily:

class C:
    # There's no @classmethod decorator here as there should have been
    def __instancecheck__(self, arg):
        return False

isinstance(42, C)

The reason is that on line 372 in classobject.c there's a call to PyObject_IsInstance(self, klass).

Probably a warning would be good for the non-classmethod case.

Checked in. The recursion bug is warded off by a standard recursion check -- you'll now get an inexplicable RuntimeError exception instead of an inexplicable SegFault. :-)