Is there a particular OS/Python version you have been successful with?
I run Gentoo + Python 3.1 or 3.2.
Another possibility (more likely perhaps) is that you miscompiled the midstate module for your system... be sure to check CFLAGS in the Makefile.