Buenas, prueba con este código, te lo incluirá todo dentro del mismo .exe (sin el zip ) y no deberías tener problemas, yo utilizo este código en is proyectos y me va bien:
from distutils.core import setup
import py2exe
setup(
windows=[
{'script': 'main.py',
"icon_resources": [(0, "un_icono.ico"),(1, "un_icono.ico")],
"name":'Nombre de tu aplicación',
"version":'0.1',
"description":'Descripción de tu aplicación',
"author":'tu_nombre',
"author_email":'tu_mail',
"url":'tu_web'}],
options={
"py2exe":{
"unbuffered": True,
"optimize": 2,
"bundle_files":1
}
}
)
Te pondría un enlace a la URL donde ese ecplican todos estos parámetros pero los derechos del foro, no me lo permiten, saludos...