I get different backtraces if I try to remove the packages one by one

Here's a trace from trying to rpm -e kernel-smp-devel-2.6.12 (which just matched
one installed package)

[root@slartibartfast /]# gdb rpm /core.1955
GNU gdb Red Hat Linux (6.3.0.0-1.122rh)
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "i386-redhat-linux-gnu"...Using host libthread_db
library "/lib/libthread_db.so.1".

Reading symbols from shared object read from target memory...done.
Loaded system supplied DSO at 0xdca000
Core was generated by `rpm -v -e kernel-smp-devel-2.6.12'.
Program terminated with signal 11, Segmentation fault.

warning: svr4_current_sos: Can't read pathname for load map: Input/output error

Reading symbols from /usr/lib/librpm-4.4.so...Reading symbols from
/usr/lib/debug/usr/lib/librpm-4.4.so.debug...done.
done.
Loaded symbols for /usr/lib/librpm-4.4.so
Reading symbols from /usr/lib/librpmdb-4.4.so...Reading symbols from
/usr/lib/debug/usr/lib/librpmdb-4.4.so.debug...done.
done.
Loaded symbols for /usr/lib/librpmdb-4.4.so
Reading symbols from /lib/libselinux.so.1...done.
Loaded symbols for /lib/libselinux.so.1
Reading symbols from /usr/lib/librpmio-4.4.so...Reading symbols from
/usr/lib/debug/usr/lib/librpmio-4.4.so.debug...done.
done.
Loaded symbols for /usr/lib/librpmio-4.4.so
Reading symbols from /usr/lib/libpopt.so.0...Reading symbols from
/usr/lib/debug/usr/lib/libpopt.so.0.0.0.debug...done.
done.
Loaded symbols for /usr/lib/libpopt.so.0
Reading symbols from /usr/lib/libsqlite3.so.0...done.
Loaded symbols for /usr/lib/libsqlite3.so.0
Reading symbols from /usr/lib/libelf.so.1...done.
Loaded symbols for /usr/lib/libelf.so.1
Reading symbols from /usr/lib/libbeecrypt.so.6...done.
Loaded symbols for /usr/lib/libbeecrypt.so.6
Reading symbols from /usr/lib/libneon.so.25...done.
Loaded symbols for /usr/lib/libneon.so.25
Reading symbols from /lib/libm.so.6...done.
Loaded symbols for /lib/libm.so.6
Reading symbols from /lib/libdl.so.2...done.
Loaded symbols for /lib/libdl.so.2
Reading symbols from /usr/lib/libz.so.1...done.
Loaded symbols for /usr/lib/libz.so.1
Reading symbols from /lib/librt.so.1...done.
Loaded symbols for /lib/librt.so.1
Reading symbols from /lib/libpthread.so.0...done.
Loaded symbols for /lib/libpthread.so.0
Reading symbols from /usr/lib/libbz2.so.1...done.
Loaded symbols for /usr/lib/libbz2.so.1
Reading symbols from /lib/libc.so.6...done.
Loaded symbols for /lib/libc.so.6
Reading symbols from /lib/libsepol.so.1...done.
Loaded symbols for /lib/libsepol.so.1
Reading symbols from /lib/libgcc_s.so.1...done.
Loaded symbols for /lib/libgcc_s.so.1
Reading symbols from /usr/lib/libstdc++.so.6...done.
Loaded symbols for /usr/lib/libstdc++.so.6
Reading symbols from /lib/libssl.so.6...done.
Loaded symbols for /lib/libssl.so.6
Reading symbols from /lib/libcrypto.so.6...done.
Loaded symbols for /lib/libcrypto.so.6
Reading symbols from /usr/lib/libgssapi_krb5.so.2...done.
Loaded symbols for /usr/lib/libgssapi_krb5.so.2
Reading symbols from /usr/lib/libkrb5.so.3...done.
Loaded symbols for /usr/lib/libkrb5.so.3
Reading symbols from /usr/lib/libk5crypto.so.3...done.
Loaded symbols for /usr/lib/libk5crypto.so.3
Reading symbols from /usr/lib/libkrb5support.so.0...done.
Loaded symbols for /usr/lib/libkrb5support.so.0
Reading symbols from /lib/libcom_err.so.2...done.
Loaded symbols for /lib/libcom_err.so.2
Reading symbols from /lib/libresolv.so.2...done.
Loaded symbols for /lib/libresolv.so.2
Reading symbols from /lib/libexpat.so.0...done.
Loaded symbols for /lib/libexpat.so.0
Reading symbols from /lib/ld-linux.so.2...done.
Loaded symbols for /lib/ld-linux.so.2
Reading symbols from /lib/libsetrans.so.0...done.
Loaded symbols for /lib/libsetrans.so.0
#0  0x002cbfeb in strlen () from /lib/libc.so.6
(gdb) bt
#0  0x002cbfeb in strlen () from /lib/libc.so.6
#1  0x007fb792 in doLookup (cache=0x8380030,
    dirName=0x7273752f <Address 0x7273752f out of bounds>,
    baseName=0x90646191 "fig", scareMemory=1) at fprint.c:76
#2  0x007fbc34 in fpLookupList (cache=0x8380030, dirNames=0x83896f0,
    baseNames=0x8fd69008, dirIndexes=0x8f52a008, fileCount=2161028,
    fpList=0x8dc6e008) at fprint.c:250
#3  0x00808d30 in rpmdbFindFpListExclude (db=0x81ee728, fpList=0x82ac470,
    matchList=0x8374ff8, numItems=7422, exclude=470) at rpmdb.c:3494
#4  0x00171565 in rpmtsRun (ts=0x81ee4f0, okProbs=0x0,
    ignoreSet=RPMPROB_FILTER_NONE) at transaction.c:1753
#5  0x0015d12f in rpmErase (ts=0x81ee4f0, ia=0x195fc0, argv=0x81d4150)
    at rpminstall.c:845
#6  0x0804beee in main (argc=4, argv=0xbfe955e4) at ./rpmqv.c:749
#7  0x002777e4 in __libc_start_main () from /lib/libc.so.6
#8  0x0804a941 in _start ()
(gdb)

One more try, different trace:

[root@slartibartfast /]# gdb rpm /core.1933
GNU gdb Red Hat Linux (6.3.0.0-1.122rh)
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "i386-redhat-linux-gnu"...Using host libthread_db
library "/lib/libthread_db.so.1".

Reading symbols from shared object read from target memory...done.
Loaded system supplied DSO at 0x41e000
Core was generated by `rpm -vv -e kernel-smp-devel-2.6.14-1.1637_FC4'.
Program terminated with signal 11, Segmentation fault.

warning: svr4_current_sos: Can't read pathname for load map: Input/output error

Reading symbols from /usr/lib/librpm-4.4.so...Reading symbols from
/usr/lib/debug/usr/lib/librpm-4.4.so.debug...done.
done.
Loaded symbols for /usr/lib/librpm-4.4.so
Reading symbols from /usr/lib/librpmdb-4.4.so...Reading symbols from
/usr/lib/debug/usr/lib/librpmdb-4.4.so.debug...done.
done.
Loaded symbols for /usr/lib/librpmdb-4.4.so
Reading symbols from /lib/libselinux.so.1...done.
Loaded symbols for /lib/libselinux.so.1
Reading symbols from /usr/lib/librpmio-4.4.so...Reading symbols from
/usr/lib/debug/usr/lib/librpmio-4.4.so.debug...done.
done.
Loaded symbols for /usr/lib/librpmio-4.4.so
Reading symbols from /usr/lib/libpopt.so.0...Reading symbols from
/usr/lib/debug/usr/lib/libpopt.so.0.0.0.debug...done.
done.
Loaded symbols for /usr/lib/libpopt.so.0
Reading symbols from /usr/lib/libsqlite3.so.0...done.
Loaded symbols for /usr/lib/libsqlite3.so.0
Reading symbols from /usr/lib/libelf.so.1...done.
Loaded symbols for /usr/lib/libelf.so.1
Reading symbols from /usr/lib/libbeecrypt.so.6...done.
Loaded symbols for /usr/lib/libbeecrypt.so.6
Reading symbols from /usr/lib/libneon.so.25...done.
Loaded symbols for /usr/lib/libneon.so.25
Reading symbols from /lib/libm.so.6...done.
Loaded symbols for /lib/libm.so.6
Reading symbols from /lib/libdl.so.2...done.
Loaded symbols for /lib/libdl.so.2
Reading symbols from /usr/lib/libz.so.1...done.
Loaded symbols for /usr/lib/libz.so.1
Reading symbols from /lib/librt.so.1...done.
Loaded symbols for /lib/librt.so.1
Reading symbols from /lib/libpthread.so.0...done.
Loaded symbols for /lib/libpthread.so.0
Reading symbols from /usr/lib/libbz2.so.1...done.
Loaded symbols for /usr/lib/libbz2.so.1
Reading symbols from /lib/libc.so.6...done.
Loaded symbols for /lib/libc.so.6
Reading symbols from /lib/libsepol.so.1...done.
Loaded symbols for /lib/libsepol.so.1
Reading symbols from /lib/libgcc_s.so.1...done.
Loaded symbols for /lib/libgcc_s.so.1
Reading symbols from /usr/lib/libstdc++.so.6...done.
Loaded symbols for /usr/lib/libstdc++.so.6
Reading symbols from /lib/libssl.so.6...done.
Loaded symbols for /lib/libssl.so.6
Reading symbols from /lib/libcrypto.so.6...done.
Loaded symbols for /lib/libcrypto.so.6
Reading symbols from /usr/lib/libgssapi_krb5.so.2...done.
Loaded symbols for /usr/lib/libgssapi_krb5.so.2
Reading symbols from /usr/lib/libkrb5.so.3...done.
Loaded symbols for /usr/lib/libkrb5.so.3
Reading symbols from /usr/lib/libk5crypto.so.3...done.
Loaded symbols for /usr/lib/libk5crypto.so.3
Reading symbols from /usr/lib/libkrb5support.so.0...done.
Loaded symbols for /usr/lib/libkrb5support.so.0
Reading symbols from /lib/libcom_err.so.2...done.
Loaded symbols for /lib/libcom_err.so.2
Reading symbols from /lib/libresolv.so.2...done.
Loaded symbols for /lib/libresolv.so.2
Reading symbols from /lib/libexpat.so.0...done.
Loaded symbols for /lib/libexpat.so.0
Reading symbols from /lib/ld-linux.so.2...done.
Loaded symbols for /lib/ld-linux.so.2
Reading symbols from /lib/libsetrans.so.0...done.
Loaded symbols for /lib/libsetrans.so.0
#0  0x007fbc15 in fpLookupList (cache=0x9d44790, dirNames=0x9d47490,
    baseNames=0x9d474a8, dirIndexes=0x9d47538, fileCount=35, fpList=0x9d475c8)
    at fprint.c:250
250                 fpList[i] = doLookup(cache, dirNames[dirIndexes[i]],
baseNames[i],
(gdb) bt
#0  0x007fbc15 in fpLookupList (cache=0x9d44790, dirNames=0x9d47490,
    baseNames=0x9d474a8, dirIndexes=0x9d47538, fileCount=35, fpList=0x9d475c8)
    at fprint.c:250
#1  0x00808d30 in rpmdbFindFpListExclude (db=0x9b8df78, fpList=0x9c4f398,
    matchList=0x9d234d0, numItems=7786, exclude=622) at rpmdb.c:3494
#2  0x00171565 in rpmtsRun (ts=0x9b88508, okProbs=0x0,
    ignoreSet=RPMPROB_FILTER_NONE) at transaction.c:1753
#3  0x0015d12f in rpmErase (ts=0x9b88508, ia=0x195fc0, argv=0x9b6e150)
    at rpminstall.c:845
#4  0x0804beee in main (argc=4, argv=0xbfcfa194) at ./rpmqv.c:749
#5  0x00cc17e4 in __libc_start_main () from /lib/libc.so.6
#6  0x0804a941 in _start ()
(gdb)

If you build an rpm with Patch12 backed out (comment out %patch12 line) does it
work?

Okay, I rebuilt rpm with Patch12 removed

When I did that, both single uninstalls of kernel-smp-devel and --allmatches
uninstall of the 9 remaining kernel-smp-devel packages worked

This bug report may well be bogus / due to bad memory. I started getting kernel
panics on the box shortly after these rpm issues started popping up, and
memtest86+ turned up a flaky DIMM

The sigsegv was probably hit as without that patch we use a lot more memory in
the fingerprint routines and if you had flaky memory anyway it possibly got
triggered by that.

For now in rawhide I've dropped the patch as for the case of large no. of
kernels installed it is very memory heavy.