I'm running the same distro as Leger and I was having the same problem.
Now I've applied dbm.diff and with a clean build I'm seeing this:

building '_dbm' extension
gcc -pthread -fPIC -fno-strict-aliasing -DNDEBUG -g -fwrapv -O3 -Wall
-Wstrict-prototypes -DHAVE_GDBM_DASH_NDBM_H -I.
-I/home/andy/src/python3/Python-3.0/./Include -I. -IInclude -I../Include
-I/usr/local/include -I/home/andy/src/python3/Python-3.0/debug/Include
-I/home/andy/src/python3/Python-3.0/debug -c
/home/andy/src/python3/Python-3.0/Modules/_dbmmodule.c -o
build/temp.linux-i686-3.0/home/andy/src/python3/Python-3.0/Modules/_dbmmodule.o
gcc -pthread -shared
build/temp.linux-i686-3.0/home/andy/src/python3/Python-3.0/Modules/_dbmmodule.o
-L/usr/local/lib -lgdbm -o build/lib.linux-i686-3.0/_dbm.so
*** WARNING: renaming "_dbm" since importing it failed:
build/lib.linux-i686-3.0/_dbm.so: undefined symbol: dbm_firstkey