First, is it only with 2.7 or 2.6?
Second, I don't really get the point of the FIPS mode. The PDF you linked to seems full of bureaucratic jargon.
Third, I can't reproduce under Mandriva, but perhaps it's because it's using OpenSSL 1.0.0 (which the PDF says isn't supported).
Fourth, if MD5 is insecure and FIPS disables insecure algorithm, then why should hashlib allow MD5 hashing when FIPS mode is enabled?
Fifth, please take a look at the OpenSSL initialization routine in _sslmodule.c and try to transplant it to the hashlib initialization routine:

    /* Init OpenSSL */
    SSL_load_error_strings();
    SSL_library_init();
    OpenSSL_add_all_algorithms();