Прежде всего, вы уверены, что строка на самом деле находится в файле .exe, а не в файле library.zip? Если строка находится в файле library.zip, вам будет намного легче. В соответствии с часто задаваемыми вопросами по py2exe (http://www.py2exe.org/index.cgi/FAQ) ваш сценарий ввода будет скомпилирован байтово и встроен в качестве ресурса в .exe, а остальные импортируемые им модули Python будут находиться в файле library.zip.
Предполагая, что строка равна в вашем сценарии ввода, процесс байтовой компиляции (который, я считаю, использует модуль маршала) должен оставить фактическое содержимое строки как ASCII или UTF-8. Строка, которую вы ищете, длиннее, чем символ «6», который вы ищете? Я думаю, что вы, вероятно, просто меняете неправильную строку (или что-то, что даже не является частью строки, что может быть очень плохо). Если вы уверены, что он выглядит правильно (т.е. строка имеет длину не менее 5 или 6 символов и очень различима), может ли это произойти в файле несколько раз, и вы изменили неправильный экземпляр?
Если вы хотите пойти дальше, вы можете получить редактор ресурсов Windows и извлечь ресурсы из .exe для восстановления файла .pyo, а затем использовать модули marshal и dis для преобразования байт-кода обратно в коды операций и литералы Python. Это может дать вам лучшее представление о том, какие строки находятся в файле:
http://nedbatchelder.com/blog/200804/the_structure_of_pyc_files.html