Созданный на бумаге архитектурный ансамбль был представлен Николаю I в 1836 году и получил высочайшее одобрение. Штакеншнейдер настолько угодил царю, что тот даже рекомендовал использовать стилистическую основу Коломенского дворца при разработке проекта другой императорской резиденции – Большого Кремлевского дворца, которым занимался в то время Константин Тон. Это означало более чем высокую оценку усилий Штакеншнейдера, поскольку Тон считался основоположником собственного стиля – русско-византийского.
Вторая половина 1830-х годов – это время интенсивного строительства в Москве, кроме Большого Кремлевского дворца, на Волхонке в тот период началось возведение многострадального храма Христа Спасителя по проекту того же Тона. Первая попытка строительства храма на Воробьевых горах завершилась неудачей и стоила казне огромных и зря понесенных расходов, за что к уголовной ответственности привлекли архитектора Александра Витберга. Неудивительно, что Николай I смотрел, как говорится, в оба за тем, как идет строительство и куда направляются государственные деньги. Проект Штакеншнейдера стоил больше, чем возведение Большого Кремлевского дворца и храма Христа Спасителя, вместе взятых. Даже при условии использования кирпича от недостроенного Царицынского дворца, вероятность чего рассматривалась. Поэтому очевидным явилось решение о некоторой отсрочке начала строительства в Коломенском.
Но, как известно, то, что объявлено временным, обладает всеми признаками постоянства. Строительство храма на Волхонке затянулось, став одним из самым длинных за всю историю наблюдений: храм был освящен лишь в 1883 году. Дворец в Кремле отстроили раньше, к 1849 году.
Учитывая масштабное строительство еще и петербургских царских дворцов, а также первой в России железной дороги Москва – Петербург, новые непомерные траты на осуществление грандиозного архитектурного ансамбля в Коломенском прохудившаяся казна просто не вынесла бы. А вскоре о дворце и вовсе позабыли: в 1853 году началась Крымская война.
Затянувшееся решение о начале строительства нового Коломенского дворца отсрочило разборку старого дворца Евграфа Тюрина, который, однако, не сидел сложа руки, занимаясь реставрацией ветшающих строений государева села. С 1832 года архитектор работает над восстановлением разного рода утраченных деталей оформления Казанского храма, в частности образа Всех Святых, предлагая «имеющийся образ святых, написанный на стене паперти сверх места царского сохранить во всей целостности, заделав оный временно щитами». А в конце 1830-х годов его внимание отвлечено на ремонт крыши старых Спасских ворот Коломенского дворца, для украшения которых он самолично рисует эскизы гербов России. На одном из сохранившихся чертежей рукою зодчего выведен и царский вензель Николая I.