The 'check for updates' button doesn't upgrade anything 'automatically' or otherwise unfortunately, or more probably, fortunately (says he, never having actually tried it). I believe it simply directs you to the download. Firstly, check Tools-Server Info in admin to see what the database thinks your current versions are.
If you are indeed on 1.3.5, download the latest version, check the upgrade info there, and the FAQ's, tutorials, and the forum here for any gotchas, and then plan accordingly.

On the Newsletter Subscribe side, there are a couple of folders called 'your_template' in the install. Are you sure they've all been renamed to the name of the template you are using?