Well, the signature of PyUnicode_Encode in Python 2.4 (see 
Objects/unicodeobject.c) is:

PyObject *PyUnicode_Encode(const Py_UNICODE *s,
			   int size,
			   const char *encoding,
			   const char *errors)

which looks like it might be relevant to the problems you're seeing.  In 
2.6, the size has type Py_ssize_t instead, which should be a 64-bit type 
on 64-bit Linux.

Closing this, since it's out of date for current Python.