Reposting as an answer, to summarise:
For cx_Freeze 4.3.2, I made a change so that it would only copy modules with names which are valid Python identifiers (so they can be imported). However, win32com appears to rely on modules such as:
win32com\gen_py\E602ED16-8EF9-4F08-B09F-6F6E8306C51Bx0x1x0.py
The hyphens (-
) in the filename make it not a valid Python identifier, so it doesn't get copied. I've opened an issue for cx_Freeze. In the meantime, a workaround is to downgrade to cx_Freeze 4.3.1, which you can download from SourceForge.
Also, I think that these modules are generated when you first wrap a COM object. So make sure that you run your code before freezing it.