The problem still exists in 2.5.1.

The explanations given so far are not correct. With x.py as before (see 
attached):

>>> import sys, gc, x
creating X('new')
creating X('old')
>>> del x,sys.modules['x']
deleting X('old')
>>> gc.collect()
deleting X('new')
6

which shows that the cycles in x module are resolvable by GC.

The problem is not that there are uncollectable objects but that GC is 
ran on exit before x becomes dead.

>>> import sys, gc, x
creating X('new')
creating X('old')
>>> gc.set_debug(1)
>>> sys.exit()
gc: collecting generation 2...
gc: objects in each generation: 463 2034 0
gc: done.
deleting X('old')


Looking at the comments in Py_Finalize, it looks like GvR intended to 
run GC after destroying the modules, but it led to problems:
(from svn blame Python/pythonrun.c)
 32278 gvanrossum 
  9025      guido       /* Destroy all modules */
  8403      guido       PyImport_Cleanup();
  9025      guido 
 32278 gvanrossum       /* Collect final garbage.  This disposes of 
cycles created by
 34776    tim_one        * new-style class definitions, for example.
 34776    tim_one        * XXX This is disabled because it caused too 
many problems.  If
 34776    tim_one        * XXX a __del__ or weakref callback triggers 
here, Python code has
 34776    tim_one        * XXX a hard time running, because even the sys 
module has been
 34776    tim_one        * XXX cleared out (sys.stdout is gone, 
sys.excepthook is gone, etc).
 34776    tim_one        * XXX One symptom is a sequence of information-
free messages
 34776    tim_one        * XXX coming from threads (if a __del__ or 
callback is invoked,
 34776    tim_one        * XXX other threads can execute too, and any 
exception they encounter
 34776    tim_one        * XXX triggers a comedy of errors as subsystem 
after subsystem
 34776    tim_one        * XXX fails to find what it *expects* to find 
in sys to help report
 34776    tim_one        * XXX the exception and consequent unexpected 
failures).  I've also
 34776    tim_one        * XXX seen segfaults then, after adding print 
statements to the
 34776    tim_one        * XXX Python code getting called.
 34776    tim_one        */
 34776    tim_one #if 0
 32278 gvanrossum       PyGC_Collect();
 34776    tim_one #endif

Commenting out PyGC_Collect() seems like a too radical solution because  
no module referenced cycles get collected, not even those without 
__del__.

I have not tried it yet, but it looks like a possible solution is to 
call PyGC_Collect() at the end of _PyModule_Clear.