Go to `app/etc` and find `Mage_Newsletter.xml` file. If it is not there open `Mage_All.xml` and find

    <Mage_Newsletter>
        <active>true</active>
        <codePool>core</codePool>
        <depends>
            <Mage_Core/>
            <Mage_Customer/>
            <Mage_Eav/>
            <Mage_Widget/>
        </depends>
    </Mage_Newsletter>

If its not there add it. Also check if module Newsletter is present in `app/code/core/Mage`.

**Update 1**

Check if `\app\code\core\Mage\Newsletter\etc\adminhtml.xml` is present and if it has some content. All problems that you described could happen if it is missed.

**Update 2**

Go to `System > Configuration > ADVANCED > Advanced > Modules output` and check if it is `enabled`.