Корректор прав. Кемерово – существительное среднего рода. Если существительное обозначает географический объект, то его род определяется родом слова, которое обозначает тип объекта (город, река, озеро и т. д.) – такое правило, действительно, существует, но касается только несклоняемых существительных (Тбилиси мужского рода, так как это город, Миссисипи женского рода, так как это река). Кемерово – изменяемое слово (в Кемерове, из Кемерова). Ср.: Москва – слово женского рода, хотя это тоже город.

С прописной буквы пишутся все географические названия, в том числе образные, поэтические, неофициальные, неточные, а также названия стран света в роли наименований разных территорий.

Рекомендуемое написание в разных ответах неодинаково, потому что неодинаков контекст. Согласно словарю В. В. Лопатина, И. В. Нечаевой, Л. К. Чельцовой «Прописная или строчная?» слово долина пишется со строчной буквы, если употребляется в прямом значении – 'впадина между горами или холмами', например: Араратская долина, Ферганская долина. Логично предположить, что если собственное наименование выдумано, но слово долина употреблено в прямом значении, его также корректно писать со строчной, а собственное имя – с прописной, именно этим объясняется наша рекомендация писать долина Звенящей Тишины (по аналогии с названием мыс Доброй Надежды).

Однако в некоторых названиях природных зон, а также в названиях мемориальных сооружений, административных территорий, населенных пунктов слово долина пишется с большой буквы: Долина гейзеров (на Камчатке), Долина царей (в Египте), Долина Славы (мемориальное сооружение), Долина Смерти (в Калифорнии) – такова словарная фиксация.

На наш взгляд, в Вашем случае корректно писать Долина бабочек, т. к. это не географический термин, а образное название природной зоны (природной достопримечательности).

Астанский – устаревшая рекомендация. Название Астана относительно новое, и прилагательные от него образовывались разными способами. Эти колебания нашли отражение в словарях. Согласно словарю Е. А. Левашова «Географические названия» (СПб., 2000) от слова Астана образуются прилагательные астанинский и астанийский. Современный академический орфографический словарь фиксирует только вариант астанинский, который, по-видимому, получил более широкое распространение. Прилагательное астанайский закрепилось в церковной сфере. Официальные названия – Астанайская епархия и митрополит Астанайский.

Правило, на которое Вы ссылаетесь, – орфографическое. Оно регулирует только выбор гласной буквы в прилагательных на -нский, образованных от имен собственных.