I've tried, I really have, but I can't come up with a solution to this.

Have a look at
 http://www.w3.org/TR/xslt#section-Creating-Elements-with-xsl:element

Try something like
  <xsl:template match="*">
    <xsl:element name="{local-name()}" namespace="http://wibble.com/ns">
      <xsl:copy-of select="@*/>
      <xsl:apply-templates/>
    </xsl:element>
  </xsl:template>

Add identity templates for PI and comments and/or special attribute
processing at leisure.