We have no problem signing our Python 2.6 exe's generated by Py2exe 0.6.9.
I don't know if this makes a difference, but we have a build batch file that calls py2exe and then (as part of our batch file vs. py2exe script) we sign our executable using the same technique as you.
Does this help?