Your controller rewrite XML part should look like this:

<frontend>
    <routers>
        <contacts>
            <args>
                <modules>
                    <Namespace_Modulename before="Mage_Contacts">Namespace_Modulename</Namespace_Modulename>
                </modules>
            </args>
        </contacts>
    </routers>
</frontend>

As you can see instead of using <contactsmodule> node we are here using <contacts> node. <contacts> is the router node which is used by Mage_Contacts module.

After this change is done, do not forget to flush the cache again.

It is a good practice to keep dependency in your module as shown below.

File : Namespace_Modulename.xml

<?xml version="1.0"?>
<config>
    <modules>
        <Namespace_Modulename>
            <active>true</active>
            <codePool>local</codePool>
            <depends>
                <Mage_Contacts />
            </depends>
        </Namespace_Modulename>
    </modules>
</config>

This clearly indicates that your module has a dependency on Mage_Contacts module and thus Magento will load your module only after Mage_Contacts is loaded.