Attached is a patch based on the original patch, meant to have better performance.

On my PC, this:

import sys, time, uuid

def uu(n):
    t = time.time()
    for x in range(n):
        uuid.uuid1()
    print('%.3f microseconds' % ((time.time() - t) * 1000000.0 / n))

uu(50000)

records a time of 38.5 microseconds unpatched (still using ctypes/libuuid) and a time of 16.5 microseconds afterwards.
uuid4() results in an improvement from 30 microseconds to 9 microseconds. From what I could see, what took the most time was the call to UUID() with a bytes object. That's why this patch passes in the uuid as a long.

It also fixes setup.py to check for the uuid.h header.