I've just gone down this road myself, and here are my observations and experience.
The first thing to know is that there are two valid locations for the manifest:
Embedded in the executable (or dll) as a resource
Next to the executable (or dll), as you are currently doing.
Read up about manifests here: http://msdn.microsoft.com/en-us/library/windows/desktop/aa374191(v=vs.85).aspx
In my experience, you can use both at the same time, but if there is any overlap, the embedded manifest takes precedence. This is what is screwing you up. The executable created by Pyinstaller has an embedded manifest that sets the requested execution level to "asInvoker" which overrides the level in the manifest you are using.
The --manifest (or manifest parameter to EXE() ) merely modifies the manifest that Pyinstaller places next to the executable/dll, rather than the embedded manifest.
So, we could turn to mt.exe to change the embedded manifest, but as you have found, this results in an application that doesn't run. This is because the application created by Pyinstaller are really two parts; a small executable that extracts an archive then sets up and launches your code in its bundled python environment, and that archive that the executable operates on. This works because the specification for an executable allows there to be arbitrary data appended to the end of the executable file, but outside of the executable itself, as defined by the size recorded in the executable's header. When we run mt.exe on the Pyinstaller created executable, it looks at the header to get the size, and ignores anything beyond that, thus discarding that archive data when it saves your executable with the new manifest, which results in the error you have seen.
The solution I am using is to modify the manifest before the archive data gets appended to the executable, which requires modification of the Pyinstaller source code. The Pyinstaller source has utilities to update the resources in an executable/dll, which it uses as part of its build process. You'll want to look at build.py, winmanifest.py and maybe winresource.py in your Pyinstaller location. I added a parameter to the EXE class and then a step in the assemble method of that class to update the manifest, I do this right before it appends the archive. The meat of what I added is like so:
if self.manifest_override != None:
print "Overriding default manifest"
tmpnm = tempfile.mktemp()
shutil.copy2(exe, tmpnm)
os.chmod(tmpnm, 0755)
winmanifest.UpdateManifestResourcesFromXMLFile(tmpnm, self.manifest_override, names=[1], languages=[1033])
exe = tmpnm
trash.append(tmpnm)
I have this placed right before the line that reads: exe = checkCache(exe, ...
and it should be above, but close to a print "Appending archive to EXE"...
This solution has been working for me, but I am not super happy with it. I would rather override the default manifest that gets embedded, instead of updating it, but my efforts have been fruitless thus far.
Sorry for the wall of text, but there is a lot going on here.