Убедитесь, что ваш cxFreexe установлен и работает с тем же питоном, что и приложение, которое вы хотите заморозить. Таким образом, ваш PYTHONPATH должен быть настроен правильно.
Исключение составляют случаи, когда скрипт, который вы хотите заморозить, сам изменяет путь Python. В этом случае перед замораживанием вам нужно сделать те же самые изменения самостоятельно.