This patch (surprisingly) seems to do the job quite nicely:

diff -r 1280b38fe583 Lib/test/test_os.py
--- a/Lib/test/test_os.py	Tue Oct 16 23:14:03 2012 +1000
+++ b/Lib/test/test_os.py	Tue Oct 16 21:25:36 2012 +0000
@@ -40,6 +40,20 @@
     or (st.st_mtime != st[8])
     or (st.st_ctime != st[9]))
 
+try:
+    import posix
+except ImportError:
+    # Windows has nanosecond utime resolution.
+    UTIME_EPSILON = 2e-9
+else:
+    import sysconfig
+    if 'HAVE_UTIMENSAT' in posix._have_functions:
+        UTIME_EPSILON = 2e-9
+    elif 'HAVE_UTIMES' in sysconfig.get_config_vars():
+        UTIME_EPSILON = 2e-6
+    else:
+        UTIME_EPSILON = 1.0
+
 # Detect whether we're on a Linux system that uses the (now outdated
 # and unmaintained) linuxthreads threading library.  There's an issue
 # when combining linuxthreads with a failed execv call: see
@@ -312,18 +326,32 @@
         st0 = os.stat(filename)
         # Doesn't set anything new, but sets the time tuple way
         utime(filename, (attr(st0, "st_atime"), attr(st0, "st_mtime")))
-        # Setting the time to the time you just read, then reading again,
-        # should always return exactly the same times.
         st1 = os.stat(filename)
-        self.assertEqual(attr(st0, "st_mtime"), attr(st1, "st_mtime"))
-        self.assertEqual(attr(st0, "st_atime"), attr(st1, "st_atime"))
+
+        def _t(left, right, attr, name):
+            l = attr(left, name)
+            r = attr(right, name)
+            if isinstance(l, int):
+                assert isinstance(r, int)
+                l = l / 1e9
+                r = r / 1e9
+            return abs(l - r)
+
+        epsilon = UTIME_EPSILON
+        self.assertLess(_t(st0, st1, attr, "st_mtime"), epsilon)
+        self.assertLess(_t(st0, st1, attr, "st_atime"), epsilon)
+
         # Set to the current time in the old explicit way.
         os.utime(filename, None)
         st2 = os.stat(support.TESTFN)
         # Set to the current time in the new way
         os.utime(filename)
         st3 = os.stat(filename)
-        self.assertAlmostEqual(attr(st2, "st_mtime"), attr(st3, "st_mtime"), delta=delta)
+        self.assertAlmostEqual(
+            attr(st2, "st_mtime"),
+            attr(st3, "st_mtime"),
+            delta=delta
+        )
 
     def test_utime(self):
         def utime(file, times):


test_os passes on FreeBSD, Linux and Mac OS X with that applied.  However, the Solaris 10/SPARC box still fails:

AssertionError: 9.5367431640625e-07 not less than 2e-09

But it appears that build is actually picking up utimensat(), which makes the Solaris failures unrelated to the FreeBSD/NetBSD ones.  I'll do some more investigating.  Might warrant a separate issue.

Larry: thoughts on the test_os.patch as is?