Hey Mark,
Good news.  I ran across this thread that you made a post to last year.
So I added the following right before importing pythoncom
# 0 == pythoncom.COINIT_MULTITHREADED # !!!!!
sys.coinit_flags = 0
import pythoncom
lo and behold the py2exe service now works!
Since I'm still a relative noob as far as COM is concerned, can you explain what that line of code did?  I'm assuming that the exe generated by py2exe must have been running a different COM threading model than standard python?  Just trying to figure all this out...