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.