Главная трудность в написании мемуаров для Кузнецова заключалась в том, что он был лишен возможности пользоваться архивами. Как мы понимаем, никакая человеческая память не способна сохранить все нюансы прожитой жизни, тем более столь бурной, как у Кузнецова. Поэтому определенные ошибки в мемуарах были просто неизбежны, и к этому следует относиться с пониманием.
В 1964 года Кузнецов написал письмо маршалу Р. Я. Малиновскому, который стал к этому времени министром обороны. У них всегда были почти приятельские отношения, и Кузнецов надеялся на его помощь. Малиновский его принял, однако на просьбу Кузнецова ответил отказом:
— Увы, Николай Герасимович, но ваш вопрос решался самыми высшими инстанциями. К тому же Хрущев почему-то на вас сердит! — сказал он и развел руками…
После свержения Хрущева Кузнецов возобновил попытки добиться справедливости. До него дошли слухи, будто заняться его вопросом поручили маршалу М. В. Захарову. Кузнецов попытался попасть к нему на прием, но получил отказ.
Тогда Кузнецов решил обратиться, уже как член партии, напрямую в Президиум ЦК КПСС на имя Л. И. Брежнева. Он не жаловался на строгость решения Политбюро ЦК КПСС и постановления Совета Министров СССР о его освобождении от должности, однако считал неправомерным, что оба решения были приняты без его участия и предъявления ему конкретных обвинений… Кроме этого, Кузнецов писал, что не видит за собой и преступлений, которыми можно было бы объяснить лишение его звания адмирал флота Советского Союза. Принятые решения как по партийной, так и государственной линиям нельзя признать законными, так как они были приняты заочно, без заслушивания его объяснений. Никакого ответа на свое письмо он так и не получил.
При этом, как и все отставные генералы и адмиралы, в 1968 году Кузнецов был награжден юбилейной медалью «50 лет Вооруженных Сил СССР». В том же году поляки наградили отставного вице-адмирала медалью «За вашу и нашу свободу». Несколько лет спустя о нем вспомнили и монголы, наградив его своим орденом «За боевые заслуги».
Следует отметить, что пенсия у Кузнецова была весьма небольшой и семья жила скромно. Стремительное увольнение в отставку создало немало трудностей. Сколько-нибудь значительных накоплений у Кузнецовых не было. Два сына еще учились в школе. Найти постоянную работу было сложно: «…все с подозрением смотрели на меня — как бы чего не вышло». Узнав в 1968 году о постановлении Совета Министров СССР о пересмотре пенсий Героям Советского Союза, он позвонил Горшкову, и тот пообещал возбудить ходатайство. Однако дело продвигалось медленно. Только в мае министр обороны А. А. Гречко написал в ЦК бумагу с просьбой увеличить пенсию Кузнецову.
Казалось бы, дело решено. Но неожиданно Кузнецову перезвонил заведующий административным отделом ЦК КПСС Н. И. Савинкин, который сообщил, что для решения пенсионного вопроса ему необходимо снять выговор по партийной линии. Кузнецов знать не знал об этом взыскании.
Вскоре после этого он был принят Савинкиным. Тот издали показал Кузнецову решение о вынесении ему партийного взыскания от 1956 года, но ознакомиться с его основаниями не разрешил, блюдя «партийную тайну». От себя же посоветовал написать министру обороны Гречко и начальнику Главного политуправления генералу Епишеву. В Министерстве обороны накладывали взыскание, они и должны его снять.
Кузнецов немедленно направил письма в оба адреса с просьбой поддержать ходатайство о снятии партийного взыскания, а также обращение в ЦК КПСС с просьбой объяснить основания, по которым взыскание было наложено даже без его уведомления.
Спустя некоторое время Кузнецова принял председатель Комитета партийного контроля при ЦК КПСС А. Я. Пельше, который объявил ему, что партийное взыскание с него снято. Пользуясь случаем, Кузнецов попытался передать письмо Брежневу с просьбой разобраться в его деле, а также разрешить ознакомиться с материалами, на основании которых он понижен в звании, но Пельше отказался. Единственным результатом его усилий оказалась прибавка к пенсии, которая теперь составила 380 рублей — сумма для 1970-х годов вполне неплохая.
