Мне cxFreeze показался не настолько интуитивно-понятным.
Я без особых проблем использовал py2exe. С помощью него 100% exe работает на любой машине. Но я так понял он слабо развивается и под питон 3 его нет. А так как в вашем случае версии питона не выше 2.7, то подойдет.
Но если так хочется pyinstaller-2.0, то скорее всего сборка проводится без какого-то параметра, который указывает, чтобы сборка была независимой, поэтому:
4kpt
Могу скинуть алгоритм с рисунками, как это правильно делать
Хотелось бы увидеть.
P.S. Лучше конечно начать пользоваться cxFreeze как советует
4kpt, так как у них допилено даже до Python 3.3, что говорит о том, что продукт живой.