Provided you're site is using a single (non-English) language, and you've installed the content type modules before you enabled the translation module, you have this problem because the strings with the content names are already imported into Drupal and any translation done after that point in the translation interface will not have any effect (unless you uninstall the content type, and then reinstall it again).
Instead of toggling installation (which may wipe out any content associated with the content type), navigate to Administration » Structure » Content types and click Edit for the content type you want to translate.
There you will see the human-readable name of the content type in a text field. Edit this field to the translated string you want, and click Save content type.
(The same goes for the other fields that appear in the content type UI, such as "Description" and field names.)
However, if your site is multi-language, I really think this is a bug in the Internationalization module, and as such is off-topic here. See Translate interface for nodes, fields, etc. show wrong language in the column for the issue.
However, I was able to get the node types translated at my site by doing the following:
First, I made sure that I installed the Internationalization module before I added any languages. I also made sure that I used English as the default language all the way during the translation process.
So you do the following with English as the only language enabled (if you've got additional languages enabled, uninstall them, you will also need to disable and uninstall the Internationalization module and all its helper modules to get a clean start):
- Download and install the [Internationalization] project.
- Enable the Multilingual content module.
Then add any additional languages you want, but do not enable them. This is supposed to add translations for the Node types, but this may not happen (due to the bug I mentioned initially).
You can confirm this by looking under the "Overview" tab of the translation interface:
If the percentage in the "Node types" for your second language is ("Norwegian Bokmål" in the image above) is 0%, the translated strings for the Node types has not been imported into the translation interface, and after you enable that language, the English strings will appear since there are no translated strings yet.
However, it should now be possible to add these translation by hand. Navigate to the translate tab of the translation interface, and limit search to Node types.
The strikethrough over the string with the two letters in the Languages column means that the translation is missing. Click "edit" to add the missing translation.
This exact procedure fixed it for me as can be seen from the "Overview" tab below. The percentage for "Node types" for "Norwegian Bokmål" in now 100%.
After doing all the above, it is OK to set a non-English language as default.