Michael,
 
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?
 
Malcolm