Can I re-sign an .apk with a different certificate than what it came with?

try this

1) Change the extension of your .apk to .zip

2) Open and remove the folder META-INF

3) Change the extension to .apk

4) Use the jarsigner and zipalign with your new keystore.

hope it helps