Hi,
In theme.skin you can control headings in a way that overrides the module settings.
<portal:ModuleTitleControl runat="server"
UseModuleHeading="false"
UseModuleHeadingOnSideColumns="false"
DetectSideColumn="true"
Element="h1"
SideColumnElement="h2"
LiteralExtraTopContent=""
LiteralExtraBottomContent=""
ExtraCssClasses=""
SideColumnExtraCssClasses=""
/>
The key here is UseModuleHeading="false" which means it will use the theme.skin settings instead of the module settings or web.config setting. If that was set to true then what you did should work but with false it will use the other settings from theme.skin for Element and SideColumnElement. Note for example in the above case it will use h1 for center pane content and h2 for side content.
Hope that helps,
Joe