Hi Jenny
This is the crucial part from the themes documentation:
Just to explain what this is, I’ll use an example based on the ‘Newsletters’ Module. When Newsletter looks for themes for ‘Newsletters’ Module, it first searches themes inside the natural theme folder, wp-content/plugins/newsletter/emails/themes. Then it scans a second folder at wp-content/extensions/newsletter/emails/themes. The folder wp-content/extensions/newsletter is a parallel version of the original plugin folder, and Newsletter treats both folders as if they were only one folder, by merging the contents of both folders together.
Basically you need to create a folder wp-content/extensions/newsletter/emails/themes and put your theme there…
The reason, as Stefano mentioned, is that WordPress Updates work like this: The complete Plugin folder is deleted and replaced with the content of the updated plugin. This is general WordPress behaviour and not specific to the newsletter plugin. Any plugin that saves data in a subfolder of the plugin folder will face the same problem.
Mike