Go to app/etcapp/etc
and find Mage_Newsletter.xmlMage_Newsletter.xml
file. If it is not there open Mage_All.xmlMage_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
.