Solutions:
Solution 1. In building the package in the console you include a package using --packages arg.
C:\myapp\>C:\Python26\python.exe setup.py py2exe --packages encodings
Solution 2. You can also include the package in your setup file
from distutils.core import setup
import py2exe
import sys
sys.argv.append("-p encodings")
and then run
C:\myapp\>C:\Python26\python.exe setup.py py2exe
