Use unicode (hope it's right, I can't test it)
diff --git a/Modules/nismodule.c b/Modules/nismodule.c
index 0811430..859042f 100644
--- a/Modules/nismodule.c
+++ b/Modules/nismodule.c
@@ -115,8 +115,8 @@
 		    if (invallen > 0 && inval[invallen-1] == '\0')
 			invallen--;
 		}
-		key = PyString_FromStringAndSize(inkey, inkeylen);
-		val = PyString_FromStringAndSize(inval, invallen);
+		key = PyUnicode_FromStringAndSize(inkey, inkeylen);
+		val = PyUnicode_FromStringAndSize(inval, invallen);
 		if (key == NULL || val == NULL) {
 			/* XXX error -- don't know how to handle */
 			PyErr_Clear();
@@ -146,7 +146,7 @@
 	if ((err = yp_get_default_domain(&domain)) != 0)
 		return nis_error(err);
 
-	res = PyString_FromStringAndSize (domain, strlen(domain));
+	res = PyUnicode_FromStringAndSize (domain, strlen(domain));
 	return res;
 }
 
@@ -178,7 +178,7 @@
 	    len--;
 	if (err != 0)
 		return nis_error(err);
-	res = PyString_FromStringAndSize (match, len);
+	res = PyUnicode_FromStringAndSize (match, len);
 	free (match);
 	return res;
 }
@@ -398,7 +398,7 @@
 	if ((list = PyList_New(0)) == NULL)
 		return NULL;
 	for (maps = maps; maps; maps = maps->next) {
-		PyObject *str = PyString_FromString(maps->map);
+		PyObject *str = PyUnicode_FromString(maps->map);
 		if (!str || PyList_Append(list, str) < 0)
 		{
 			Py_DECREF(list);