I've made some further investigation on this issue. Here's the output and the stack trace using --with-pydebug (and the attached patch applied):

    run no. 0
    [8766 refs]
    free_list[0]->ob_refcnt before XDECREF: 2
    run no. 1
    [8844 refs]
    free_list[0]->ob_refcnt before XDECREF: 1
    Fatal Python error: PyThreadState_Get: no current thread
    Aborted (core dumped)

    Thread 1 (Thread 0x7ffff7fed700 (LWP 32572)):
    #0  0x00007ffff7131425 in raise () from /lib/x86_64-linux-gnu/libc.so.6
    #1  0x00007ffff7134b8b in abort () from /lib/x86_64-linux-gnu/libc.so.6
    #2  0x00000000004086f4 in Py_FatalError (
        msg=0x5a0378 "PyThreadState_Get: no current thread")
        at Python/pythonrun.c:1631
    #3  0x000000000054120c in PyThreadState_Get () at Python/pystate.c:330
    #4  0x000000000049a13b in tupledealloc (op=0x84e3a0)
        at Objects/tupleobject.c:218
    #5  0x000000000047adf1 in _Py_Dealloc (op=0x84e3a0) at Objects/object.c:2262
    #6  0x000000000049bba9 in PyTuple_Fini () at Objects/tupleobject.c:933
    #7  0x000000000040519b in Py_Finalize () at Python/pythonrun.c:466
    #8  0x00000000004047b6 in main ()

A build of Python 2.7.3 using the same steps *does not* crash, although it shows the same curious behavior for free_list[0]->ob_refcnt:

    [8676 refs]
    free_list[0]->ob_refcnt before XDECREF: 2
    run no. 1
    [8754 refs]
    free_list[0]->ob_refcnt before XDECREF: 1
    run no. 2
    [8832 refs]
    free_list[0]->ob_refcnt before XDECREF: 1

I have no idea why it behaves like that, but it seems that the default configuration with Unicode enabled is covering some bug (because of the additional references held).

Regarding the official way to disable Unicode, I cannot build Python using --enable-unicode=no on Ubuntu 13.04. In 2.7.4, 2.7.3, 2.7.2 and 2.6.8 ./configure aborts with:

    checking what type to use for unicode... configure: error:
    invalid value for --enable-unicode. Use either ucs2 or ucs4
    (lowercase).

I'm afraid I'm missing something really obvious. With 2.5.6 I'm able to get past the configure part but then it fails when building the modules.