This reverts r63675 based on the discussion in this thread:

 http://mail.python.org/pipermail/python-dev/2008-June/079988.html

Python 2.6 should stick with PyString_* in its codebase.  The PyBytes_* names
in the spirit of 3.0 are available via a #define only.  See the email thread.
diff --git a/Modules/gdbmmodule.c b/Modules/gdbmmodule.c
index 89d9a3c..04b3332 100644
--- a/Modules/gdbmmodule.c
+++ b/Modules/gdbmmodule.c
@@ -128,10 +128,10 @@
     drec = gdbm_fetch(dp->di_dbm, krec);
     if (drec.dptr == 0) {
         PyErr_SetString(PyExc_KeyError,
-                        PyBytes_AS_STRING((PyBytesObject *)key));
+                        PyString_AS_STRING((PyStringObject *)key));
         return NULL;
     }
-    v = PyBytes_FromStringAndSize(drec.dptr, drec.dsize);
+    v = PyString_FromStringAndSize(drec.dptr, drec.dsize);
     free(drec.dptr);
     return v;
 }
@@ -155,7 +155,7 @@
     if (w == NULL) {
         if (gdbm_delete(dp->di_dbm, krec) < 0) {
             PyErr_SetString(PyExc_KeyError,
-                            PyBytes_AS_STRING((PyBytesObject *)v));
+                            PyString_AS_STRING((PyStringObject *)v));
             return -1;
         }
     }
@@ -188,14 +188,14 @@
                         "GDBM object has already been closed");
         return -1;
     }
-    if (!PyBytes_Check(arg)) {
+    if (!PyString_Check(arg)) {
         PyErr_Format(PyExc_TypeError,
                      "gdbm key must be string, not %.100s",
                      arg->ob_type->tp_name);
         return -1;
     }
-    key.dptr = PyBytes_AS_STRING(arg);
-    key.dsize = PyBytes_GET_SIZE(arg);
+    key.dptr = PyString_AS_STRING(arg);
+    key.dsize = PyString_GET_SIZE(arg);
     return gdbm_exists(dp->di_dbm, key);
 }
 
@@ -255,7 +255,7 @@
 
     key = gdbm_firstkey(dp->di_dbm);
     while (key.dptr) {
-        item = PyBytes_FromStringAndSize(key.dptr, key.dsize);
+        item = PyString_FromStringAndSize(key.dptr, key.dsize);
         if (item == NULL) {
             free(key.dptr);
             Py_DECREF(v);
@@ -306,7 +306,7 @@
     check_dbmobject_open(dp);
     key = gdbm_firstkey(dp->di_dbm);
     if (key.dptr) {
-        v = PyBytes_FromStringAndSize(key.dptr, key.dsize);
+        v = PyString_FromStringAndSize(key.dptr, key.dsize);
         free(key.dptr);
         return v;
     }
@@ -338,7 +338,7 @@
     check_dbmobject_open(dp);
     nextkey = gdbm_nextkey(dp->di_dbm, key);
     if (nextkey.dptr) {
-        v = PyBytes_FromStringAndSize(nextkey.dptr, nextkey.dsize);
+        v = PyString_FromStringAndSize(nextkey.dptr, nextkey.dsize);
         free(nextkey.dptr);
         return v;
     }
@@ -541,7 +541,7 @@
     DbmError = PyErr_NewException("gdbm.error", NULL, NULL);
     if (DbmError != NULL) {
         PyDict_SetItemString(d, "error", DbmError);
-        s = PyBytes_FromString(dbmmodule_open_flags);
+        s = PyString_FromString(dbmmodule_open_flags);
         PyDict_SetItemString(d, "open_flags", s);
         Py_DECREF(s);
     }