Thanks.

The relevant code in setup.py is all wrapped with --pydebug:
        if COMPILED_WITH_PYDEBUG or not have_usable_openssl:

All of my testing had been --with-pydebug.

Rebuilding without --with-pydebug leads to some interesting failures; as you say, if OpenSSL has md5 support disabled, this isn't going to work unless the _md5 module is manually enabled.

Notes on some of the failures seen:

$ OPENSSL_FORCE_FIPS_MODE=1 ./python 
Python 2.7.0+ (trunk:82622M, Jul  7 2010, 12:08:16) 
[GCC 4.4.3 20100422 (Red Hat 4.4.3-18)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import md5
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/david/coding/python-svn/2.7-fips/Lib/md5.py", line 10, in <module>
    from hashlib import md5
  File "/home/david/coding/python-svn/2.7-fips/Lib/hashlib.py", line 136, in <module>
    globals()[__func_name] = __get_hash(__func_name)
  File "/home/david/coding/python-svn/2.7-fips/Lib/hashlib.py", line 100, in __get_openssl_constructor
    return __get_builtin_constructor(name)
  File "/home/david/coding/python-svn/2.7-fips/Lib/hashlib.py", line 71, in __get_builtin_constructor
    import _md5
ImportError: No module named _md5

>>> import hashlib
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/david/coding/python-svn/2.7-fips/Lib/hashlib.py", line 136, in <module>
    globals()[__func_name] = __get_hash(__func_name)
  File "/home/david/coding/python-svn/2.7-fips/Lib/hashlib.py", line 100, in __get_openssl_constructor
    return __get_builtin_constructor(name)
  File "/home/david/coding/python-svn/2.7-fips/Lib/hashlib.py", line 71, in __get_builtin_constructor
    import _md5
ImportError: No module named _md5

Changing:
Index: Lib/hashlib.py
===================================================================
--- Lib/hashlib.py      (revision 82622)
+++ Lib/hashlib.py      (working copy)
@@ -134,7 +134,7 @@
     # version not supporting that algorithm.
     try:
         globals()[__func_name] = __get_hash(__func_name)
-    except ValueError:
+    except (ValueError, ImportError):
         import logging
         logging.exception('code for hash %s was not found.', __func_name)
 
indicates that it's just md5 that's not found, and enables "import hashlib" to work, albeit with a traceback upon import:
ERROR:root:code for hash md5 was not found.
Traceback (most recent call last):
  File "/home/david/coding/python-svn/2.7-fips/Lib/hashlib.py", line 136, in <module>
    globals()[__func_name] = __get_hash(__func_name)
  File "/home/david/coding/python-svn/2.7-fips/Lib/hashlib.py", line 100, in __get_openssl_constructor
    return __get_builtin_constructor(name)
  File "/home/david/coding/python-svn/2.7-fips/Lib/hashlib.py", line 71, in __get_builtin_constructor
    import _md5
ImportError: No module named _md5

"import md5" also then fails in an obscure way:
>>> import md5
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/david/coding/python-svn/2.7-fips/Lib/md5.py", line 10, in <module>
    from hashlib import md5
ImportError: cannot import name md5