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/_localemodule.c b/Modules/_localemodule.c
index ce84b27..02e9e53 100644
--- a/Modules/_localemodule.c
+++ b/Modules/_localemodule.c
@@ -119,7 +119,7 @@
         if (isupper(c))
             ul[n++] = c;
     }
-    ulo = PyBytes_FromStringAndSize((const char *)ul, n);
+    ulo = PyString_FromStringAndSize((const char *)ul, n);
     if (!ulo)
         return;
     if (string)
@@ -134,7 +134,7 @@
         if (islower(c))
             ul[n++] = c;
     }
-    ulo = PyBytes_FromStringAndSize((const char *)ul, n);
+    ulo = PyString_FromStringAndSize((const char *)ul, n);
     if (!ulo)
         return;
     if (string)
@@ -149,7 +149,7 @@
         if (isalpha(c))
             ul[n++] = c;
     }
-    ulo = PyBytes_FromStringAndSize((const char *)ul, n);
+    ulo = PyString_FromStringAndSize((const char *)ul, n);
     if (!ulo)
         return;
     if (string)
@@ -175,7 +175,7 @@
             PyErr_SetString(Error, "unsupported locale setting");
             return NULL;
         }
-        result_object = PyBytes_FromString(result);
+        result_object = PyString_FromString(result);
         if (!result_object)
             return NULL;
         /* record changes to LC_CTYPE */
@@ -190,7 +190,7 @@
             PyErr_SetString(Error, "locale query failed");
             return NULL;
         }
-        result_object = PyBytes_FromString(result);
+        result_object = PyString_FromString(result);
     }
     return result_object;
 }
@@ -216,7 +216,7 @@
        involved herein */
 
 #define RESULT_STRING(s)\
-    x = PyBytes_FromString(l->s);\
+    x = PyString_FromString(l->s);\
     if (!x) goto failed;\
     PyDict_SetItemString(result, #s, x);\
     Py_XDECREF(x)
@@ -284,9 +284,9 @@
     if (!PyArg_UnpackTuple(args, "strcoll", 2, 2, &os1, &os2))
         return NULL;
     /* If both arguments are byte strings, use strcoll.  */
-    if (PyBytes_Check(os1) && PyBytes_Check(os2))
-        return PyInt_FromLong(strcoll(PyBytes_AS_STRING(os1),
-                                      PyBytes_AS_STRING(os2)));
+    if (PyString_Check(os1) && PyString_Check(os2))
+        return PyInt_FromLong(strcoll(PyString_AS_STRING(os1),
+                                      PyString_AS_STRING(os2)));
     /* If neither argument is unicode, it's an error.  */
     if (!PyUnicode_Check(os1) && !PyUnicode_Check(os2)) {
         PyErr_SetString(PyExc_ValueError, "strcoll arguments must be strings");
@@ -368,7 +368,7 @@
             return PyErr_NoMemory();
         strxfrm(buf, s, n2);
     }
-    result = PyBytes_FromString(buf);
+    result = PyString_FromString(buf);
     PyMem_Free(buf);
     return result;
 }
@@ -563,13 +563,13 @@
         return NULL;
     /* Check whether this is a supported constant. GNU libc sometimes
        returns numeric values in the char* return value, which would
-       crash PyBytes_FromString.  */
+       crash PyString_FromString.  */
     for (i = 0; langinfo_constants[i].name; i++)
         if (langinfo_constants[i].value == item) {
             /* Check NULL as a workaround for GNU libc's returning NULL
                instead of an empty string for nl_langinfo(ERA).  */
             const char *result = nl_langinfo(item);
-            return PyBytes_FromString(result != NULL ? result : "");
+            return PyString_FromString(result != NULL ? result : "");
         }
     PyErr_SetString(PyExc_ValueError, "unsupported langinfo constant");
     return NULL;
@@ -588,7 +588,7 @@
 	char *in;
 	if (!PyArg_ParseTuple(args, "z", &in))
 		return 0;
-	return PyBytes_FromString(gettext(in));
+	return PyString_FromString(gettext(in));
 }
 
 PyDoc_STRVAR(dgettext__doc__,
@@ -601,7 +601,7 @@
 	char *domain, *in;
 	if (!PyArg_ParseTuple(args, "zz", &domain, &in))
 		return 0;
-	return PyBytes_FromString(dgettext(domain, in));
+	return PyString_FromString(dgettext(domain, in));
 }
 
 PyDoc_STRVAR(dcgettext__doc__,
@@ -615,7 +615,7 @@
 	int category;
 	if (!PyArg_ParseTuple(args, "zzi", &domain, &msgid, &category))
 		return 0;
-	return PyBytes_FromString(dcgettext(domain,msgid,category));
+	return PyString_FromString(dcgettext(domain,msgid,category));
 }
 
 PyDoc_STRVAR(textdomain__doc__,
@@ -633,7 +633,7 @@
 		PyErr_SetFromErrno(PyExc_OSError);
 		return NULL;
 	}
-	return PyBytes_FromString(domain);
+	return PyString_FromString(domain);
 }
 
 PyDoc_STRVAR(bindtextdomain__doc__,
@@ -651,7 +651,7 @@
 		PyErr_SetFromErrno(PyExc_OSError);
 		return NULL;
 	}
-	return PyBytes_FromString(dirname);
+	return PyString_FromString(dirname);
 }
 
 #ifdef HAVE_BIND_TEXTDOMAIN_CODESET
@@ -667,7 +667,7 @@
 		return NULL;
 	codeset = bind_textdomain_codeset(domain, codeset);
 	if (codeset)
-		return PyBytes_FromString(codeset);
+		return PyString_FromString(codeset);
 	Py_RETURN_NONE;
 }
 #endif
@@ -760,7 +760,7 @@
     Error = PyErr_NewException("locale.Error", NULL, NULL);
     PyDict_SetItemString(d, "Error", Error);
 
-    x = PyBytes_FromString(locale__doc__);
+    x = PyString_FromString(locale__doc__);
     PyDict_SetItemString(d, "__doc__", x);
     Py_XDECREF(x);