Did you build your own MySQL, or did you use a pre-built version? And what version? It's not clear if you're using 4.0 or 4.1. If mysql_config is returning the wrong flags, then that's a bug with MySQL.
You should be able to work around this by doing this in setup.py before the call to setup(): extra_compile_args.remove('-m64') -- http://mail.python.org/mailman/listinfo/python-list