You could help this along by both running Lib.test.test_uuid with your patch applied and reporting that it passes.

Raymond, I added you because this is about changing random functions.

Side note: This code in test_uuid.test_uuid4()

        uuids = {}
        for u in [uuid.uuid4() for i in range(1000)]:
            uuids[u] = 1
        equal(len(uuids.keys()), 1000)

could be updated to use sets rather than a fake dict:

        uuids = set()
        for u in [uuid.uuid4() for i in range(1000)]:
            uuids.add(u)
        equal(len(uuids), 1000)