I have figured out that this only happens when a python extension has a class within it that extends one of the nautilus-python classes.  This small code sample does not cause the hash warning:

import gtk
import nautilus

class Test:
    def __init__(self):
        pass

But this does:

import gtk
import nautilus

class Test(nautilus.InfoProvider):
    def __init__(self):
        pass

    def update_file_info(self, file):
        return

If you subclass and don't override any methods of the parent class, like so:

import gtk
import nautilus

class Test(nautilus.InfoProvider):
    def __init__(self):
        pass

you don't get the warning output.  The warnings may come because the NautilusFileInfo structures aren't getting free'd correctly.

The bug is caused by this code in nautilus_python_object_get_file_items:

py_ret = PyObject_CallMethod(object->instance, METHOD_PREFIX METHOD_NAME,
	 "(NN)", pygobject_new((GObject *)window), py_files);

The pygobject_new(window) is causing the leak _if_ window->ref_count == 1.  At first it looked something similar to bug 344876, but bailing out early if floating == FALSE doesn't make any difference.  I have no idea how to fix this :-/

Looks like calling Py_Finalize() takes care of this leak.  Fixed in n-p HEAD, but needs a nautilus patch.