The "overrides" attribute is a boolean (In IntelliJ 13 anyway), set it to true and the old Implementation will be removed first
<extensions defaultExtensionNs="com.intellij">
<applicationService
serviceInterface="com.intellij.openapi.wm.impl.FrameTitleBuilder"
serviceImplementation="com.my.package.MyFrameTitleBuilder"
overrides="true" />
</extensions>