If you haven't tried it export using EPUB 3.0 and let us know if it helps. Also, if you can post a sample file, using dropbox or similar, we can take a look.
This might not have something to do with InDesign. You better search on the Amazon side. Embedded fonts are not going to be displayed properly when converting from an InDesign epub to Kindle. Since the Times New Roman font is obfuscated/encrypted when embedded in the ePub via InDesign, the Kindle device can't show it, except the same font is also installed on the device or the embedded font was not obfuscated which you can't set in InDesign. ID always obfuscates/encrypts fonts in epub.
Last year, Amazon introduced a new font called Bookerly which is now the default font shown on Kindle devices. Since the words are placed absolute in the fxl epub, based on the TNR Metrics, the characters will overlap or create blanks if another font is used by the device.
You probably have made a Firmware update on your Kindle Device or updated your Software, thats why it doesn't show the Times New Roman font anymore as it should. B.t.w. this was always the case. Technically seen, your last Kindle file displayed already wrong but you didn't notice it since the font used before the Bookerly font switch, was close to the TNR font.
The solution is to crack the epub open before conversion to kindle and replace the obfuscated font files with the original (non obfuscated) ones. The name of the font files has to be identical to the the obfuscated version in the epub. Also delete the encryption.xml file in the epub, to find in the META-INF folder.
Please also check that custom font display is activated on your Kindle device.
For legal reasons, I also need to mention that you need to check the license of the fonts you embed into the epub/mobi. People often think that system fonts such as the Times New Roman can be embedded into epub/kindle without any further licensing. This is a mistake. It has not yet been complained by the copyright holder, as far as I know. Also some fonts are only allowed to be embedded when the font files are obfuscated/encrypted. Since encryption only works for epub and not for Kindle files, such licensed fonts are not allowed to be used in Kindle files or they don't show right on the device when obfuscated. If you have licensed the Times New Roman properly, please forget this last comment about legal reasons.
This is happening to me on a book I just published today. It seems that mobi doesn't recognize the font at all. Since I am not the one sending the file to KDP (a distributor is) there is no way for me to make changes. I have purchased the correct license and exported the font with the epub file. Is the only solution to not use my chosen font?
I have experienced this problem myself and found some older posts describing similar issues. The problem seems to lie in the encryption and/or obfuscation of fonts when exported from Indesign. I've run some tests on a few of my books and found that replacing the encrypted font files that are output with your file with an unencrypted version can resolve this issue.
A word of warning, though. In order to do this legally, you must find and use fonts which allow for this kind of embedding. Read the licenses carefully, as many fonts that seem to allow embedding will still require some kind of encryption.