in app/design/frontend/theme/theme/layout/newsletter.xml:

Change from :

<reference name="footer">
            <block type="newsletter/subscribe" name="footer.newsletter" as="newsletter" before="footer_store_language" template="newsletter/subscribe.phtml"/>
        </reference>

To

<reference name="left">
     <block type="newsletter/subscribe" name="left.newsletter" template="newsletter/subscribe.phtml" before="-" />
    </reference>
</default>

In app/design/frontend/theme/theme/layout/newsletter.xml change from:

<reference name="footer">
    <block type="newsletter/subscribe" name="footer.newsletter" as="newsletter" before="footer_store_language" template="newsletter/subscribe.phtml"/>
</reference>

To:

<reference name="left">
    <block type="newsletter/subscribe" name="left.newsletter" template="newsletter/subscribe.phtml" before="-" />
</reference>