If you charge ahead and use subprocess.Popen and think that sys.executable points to the right place, think again.
It actually points to your exe when frozen!
Makes for interesting recursion, so here is a fix:
Get the path luke:
Important bit reposted below. Attribution to user881185 on StackOverflow.
In case that link breaks before this blog goes away:
app_path=os.path.realpath(os.path.join(os.path.dirname(sys.executable),'test.exe')) child = subprocess.Popen(app_path)
Here is some info from the py2exe site on how to do the path in case of unicode troubles: