My searching has led me to believe that pyzmq worked with PyInstaller at one point, but I'm not sure how to get it working now.
I get the same results if I use 2.1 or pyinstaller-pyinstaller-v2.0-695-gd64c98d.zip
W: no module named zmq.device (top-level import by zmq.devices.basedevice)
W: no module named zmq.ETERM (delayed import by zmq.error)
W: no module named termios (top-level import by tty)
W: no module named zmq.backend.zmq_version_info (top-level import by zmq.sugar.version)
W: no module named _dummy_threading (top-level import by dummy_threading)
W: no module named zmq.backend.zmq_errno (delayed import by zmq.error)
W: no module named cl (delayed, conditional import by aifc)
W: no module named multiprocessing.cpu_count (top-level import by multiprocessing.dummy)
W: no module named multiprocessing.TimeoutError (top-level import by multiprocessing.pool)
W: no module named posix (conditional import by __main__)
W: no module named pwd (delayed, conditional import by posixpath)
W: no module named org (top-level import by pickle)
W: no module named zmq.PUB (top-level import by zmq.devices.monitoredqueuedevice)
W: no module named org (delayed import by xml.sax)
W: no module named zmq.backend.Context (top-level import by zmq.sugar.context)
W: no module named zmq.ZMQError (top-level import by zmq.devices.monitoredqueuedevice)
W: no module named fcntl (conditional import by subprocess)
W: no module named multiprocessing.TimeoutError (top-level import by multiprocessing.dummy)
W: no module named zmq.device (top-level import by zmq.devices)
W: no module named zmq.core (top-level import by zmq)
W: no module named zmq.backend.Frame (top-level import by zmq.sugar.frame)
W: no module named grp (top-level import by shutil)
W: no module named pwd (top-level import by shutil)
W: no module named java (conditional import by xml.sax._exceptions)
W: no module named pwd (top-level import by tarfile)
W: no module named readline (delayed import by pdb)
W: no module named _scproxy (conditional import by urllib)
W: no module named zmq.QUEUE (top-level import by zmq.devices.basedevice)
W: no module named _sysconfigdata (delayed import by distutils.sysconfig)
W: no module named zmq.Context (top-level import by zmq.devices.basedevice)
W: no module named multiprocessing.AuthenticationError (top-level import by multiprocessing.connection)
W: no module named pwd (delayed import by getpass)
W: no module named EasyDialogs (conditional import by getpass)
W: no module named termios (top-level import by getpass)
W: no module named grp (top-level import by tarfile)
W: no module named multiprocessing.dummy.Process (delayed import by __main__)
W: no module named org (top-level import by copy)
W: no module named multiprocessing.current_process (top-level import by multiprocessing.reduction)
W: no module named fcntl (top-level import by tempfile)
W: no module named readline (delayed, conditional import by cmd)
W: no module named zmq.EAGAIN (delayed import by zmq.error)
W: no module named zmq.backend.Frame (top-level import by zmq.sugar.tracker)
W: no module named zmq.ETERM (top-level import by zmq.devices.basedevice)
W: no module named zmq.backend.zmq_poll (top-level import by zmq.sugar.poll)
W: no module named _xmlplus (top-level import by xml)
W: no module named cl (delayed import by aifc)
W: no module named xmlparse (top-level import by pyexpat)
W: no module named posix (conditional import by pyi_os_path)
W: no module named zmq.backend.constants (top-level import by zmq.sugar.constants)
W: no module named multiprocessing.Pool (top-level import by multiprocessing.managers)
W: no module named multiprocessing.RLock (top-level import by multiprocessing.sharedctypes)
W: no module named multiprocessing.Process (top-level import by multiprocessing.pool)
W: no module named _xmlrpclib (top-level import by xmlrpclib)
W: no module named _emx_link (conditional import by os)
W: no module named posix (conditional import by os)
W: no module named xmltok (top-level import by pyexpat)
W: no module named rourl2path (conditional import by urllib)
W: no module named multiprocessing.Process (top-level import by multiprocessing.managers)
W: no module named multiprocessing.current_process (top-level import by multiprocessing.connection)
W: no module named pwd (delayed import by webbrowser)
W: no module named multiprocessing.Process (top-level import by zmq.devices.basedevice)
W: no module named multiprocessing.active_children (top-level import by multiprocessing.managers)
W: no module named multiprocessing.cpu_count (top-level import by multiprocessing.pool)
W: no module named SOCKS (top-level import by ftplib)
W: no module named zmq.backend.strerror (delayed import by zmq.error)
W: no module named multiprocessing.Pipe (top-level import by multiprocessing.queues)
W: no module named zmq.backend.Socket (top-level import by zmq.sugar.socket)
W: no module named multiprocessing.current_process (top-level import by multiprocessing.managers)
W: no module named zmq.ZMQError (top-level import by zmq.devices.basedevice)
W: __all__ is built strangely at line 0 - zmq (C:\Users\Therms\Envs\_deleteme\lib\site-packages\pyzmq-14.0.1-py2.7-win32.egg\zmq\__init__.pyc)
W: __all__ is built strangely at line 0 - dummy_threading (C:\Python27\Lib\dummy_threading.pyc)
W: delayed exec statement detected at line 0 - bdb (C:\Python27\Lib\bdb.pyc)
W: delayed eval hack detected at line 0 - bdb (C:\Python27\Lib\bdb.pyc)
W: delayed eval hack detected at line 0 - bdb (C:\Python27\Lib\bdb.pyc)
W: delayed __import__ hack detected at line 0 - optparse (C:\Python27\Lib\optparse.pyc)
W: delayed conditional __import__ hack detected at line 0 - doctest (C:\Python27\Lib\doctest.pyc)
W: delayed exec statement detected at line 0 - doctest (C:\Python27\Lib\doctest.pyc)
W: delayed conditional __import__ hack detected at line 0 - doctest (C:\Python27\Lib\doctest.pyc)
W: __all__ is built strangely at line 0 - tokenize (C:\Python27\Lib\tokenize.pyc)
W: __all__ is built strangely at line 0 - tokenize (C:\Python27\Lib\tokenize.pyc)
W: delayed conditional __import__ hack detected at line 0 - pyi_archive (C:\Users\Therms\Envs\_deleteme\lib\site-packages\PyInstaller\loader\pyi_archive.pyc)
W: delayed __import__ hack detected at line 0 - pickle (C:\Python27\Lib\pickle.pyc)
W: delayed __import__ hack detected at line 0 - pickle (C:\Python27\Lib\pickle.pyc)
W: delayed __import__ hack detected at line 0 - zmq.backend.select (C:\Users\Therms\Envs\_deleteme\lib\site-packages\pyzmq-14.0.1-py2.7-win32.egg\zmq\backend\select.pyc)
W: delayed conditional exec statement detected at line 0 - multiprocessing.sharedctypes (C:\Python27\Lib\multiprocessing\sharedctypes.pyc)
W: delayed __import__ hack detected at line 0 - encodings (C:\Users\Therms\Envs\_deleteme\lib\encodings\__init__.pyc)
W: delayed __import__ hack detected at line 0 - pydoc (C:\Python27\Lib\pydoc.pyc)
W: delayed __import__ hack detected at line 0 - pydoc (C:\Python27\Lib\pydoc.pyc)
W: __all__ is built strangely at line 0 - multiprocessing (C:\Python27\Lib\multiprocessing\__init__.pyc)
W: __all__ is built strangely at line 0 - dis (C:\Python27\Lib\dis.pyc)
W: __all__ is built strangely at line 0 - hashlib (C:\Python27\Lib\hashlib.pyc)
W: delayed conditional eval hack detected at line 0 - warnings (C:\Users\Therms\Envs\_deleteme\lib\warnings.pyc)
W: delayed conditional __import__ hack detected at line 0 - warnings (C:\Users\Therms\Envs\_deleteme\lib\warnings.pyc)
W: delayed conditional exec statement detected at line 0 - pyi_importers (C:\Users\Therms\Envs\_deleteme\lib\site-packages\PyInstaller\loader\pyi_importers.pyc)
W: delayed __import__ hack detected at line 0 - email (C:\Python27\Lib\email\__init__.pyc)
W: delayed __import__ hack detected at line 0 - ctypes (C:\Python27\Lib\ctypes\__init__.pyc)
W: delayed __import__ hack detected at line 0 - ctypes (C:\Python27\Lib\ctypes\__init__.pyc)
W: delayed exec statement detected at line 0 - pdb (C:\Python27\Lib\pdb.pyc)
W: delayed conditional eval hack detected at line 0 - pdb (C:\Python27\Lib\pdb.pyc)
W: delayed eval hack detected at line 0 - pdb (C:\Python27\Lib\pdb.pyc)
W: delayed conditional eval hack detected at line 0 - pdb (C:\Python27\Lib\pdb.pyc)
W: delayed eval hack detected at line 0 - pdb (C:\Python27\Lib\pdb.pyc)
W: delayed __import__ hack detected at line 0 - pkgutil (C:\Python27\Lib\pkgutil.pyc)
W: delayed conditional __import__ hack detected at line 0 - pkgutil (C:\Python27\Lib\pkgutil.pyc)
W: __all__ is built strangely at line 0 - collections (C:\Python27\Lib\collections.pyc)
W: delayed exec statement detected at line 0 - collections (C:\Python27\Lib\collections.pyc)
W: delayed conditional __import__ hack detected at line 0 - unittest.main (C:\Python27\Lib\unittest\main.pyc)
W: delayed exec statement detected at line 0 - multiprocessing.managers (C:\Python27\Lib\multiprocessing\managers.pyc)
W: delayed conditional __import__ hack detected at line 0 - unittest.loader (C:\Python27\Lib\unittest\loader.pyc)
W: delayed conditional __import__ hack detected at line 0 - unittest.loader (C:\Python27\Lib\unittest\loader.pyc)
W: delayed __import__ hack detected at line 0 - unittest.loader (C:\Python27\Lib\unittest\loader.pyc)
W: __all__ is built strangely at line 0 - __future__ (C:\Python27\Lib\__future__.pyc)
W: __all__ is built strangely at line 0 - zmq.backend (C:\Users\Therms\Envs\_deleteme\lib\site-packages\pyzmq-14.0.1-py2.7-win32.egg\zmq\backend\__init__.pyc)
W: delayed __import__ hack detected at line 0 - xml.sax (C:\Python27\Lib\xml\sax\__init__.pyc)
W: delayed eval hack detected at line 0 - gettext (C:\Python27\Lib\gettext.pyc)