В частности, в феврале 1996 года Министерство иностранных дел Украины направило вице-премьеру Украины И. Курасу проект Декларации об объявлении крымских татар «коренным народом» в пределах Украины.[384]
В конце сентября того же 1996 года госкомитет по делам национальностей и миграции направил И. Курасу предложения по принятию ВР Украины закона «О коренных народах Крыма», в котором нашли бы отражение основные требования Меджлиса.[385] Особенно активным сторонником официального признания Меджлиса в украинском руководстве был глава Минюста Украины С. Головатый, неоднократно высказывавшийся за реорганизацию крымских республиканских властей по этнически-общинному принципу.Тем не менее все эти предложения не получили в 1996 и 1997 годах дальнейшего развития, что объясняется несколькими обстоятельствами как юридического, так и политического характера. С одной стороны, требование лидеров Меджлиса объявить крымских татар «коренным народом» не могло считаться достаточно юридически обоснованным. Крымские татары не подпадают под понятие «коренной народ» в международно-правовом смысле, и украинские эксперты вынуждены с этим считаться.[386]
Кроме этого создание каких-либо особых условий для одного отдельно взятого этноса может стимулировать стремление других этнических групп и меньшинств к получению сходных прав. Следует также учитывать и то, что к 1996 году ввиду ослабления республиканского движения в Крыму украинские власти потеряли прежнюю столь острую необходимость в таких союзниках как Меджлис, а также то, что в руководстве Украины опасность вероятного «татарского сепаратизма», ощущается не менее остро, чем опасность «русскоязычного». Уже в ходе обсуждения новой Конституции автономии осенью 1995 г. Меджлису не удалось получить поддержку Киева в том, чтобы в будущем региональном парламенте Крыма были установлены квоты для крымских татар. Несмотря на то, что фракция «Курултай» прибегла к голодовке протеста после принятия Крымского Основного закона ВС Автономии, украинский парламент счел возможным согласиться с той формулировкой статьи о выборах ВС Крыма, которую предлагало парламентское большинство и которая не устраивала Меджлис.В принятой 28 июля 1996 года новой Конституции Украины проблема статуса крымских татар не получила какого-либо специального освещения. Ст.24 Основного Закона провозгласила, что «граждане имеют равные конституционные права и свободы и равны перед законом. Не может быть привилегий и ограничений по признакам расы, цвета кожи, политических, религиозных и иных убеждений, пола, этнического и социального происхождения, имущественного положения, места жительства, по языковым и иным признакам».[387]
Правда, понятие «коренного народа» все же попало в украинскую Конституцию, однако без какой-либо конкретной привязки, согласно формулировки ст. 11 «Государство содействует консолидации и развитию украинской нации, ее исторического сознания, традиций и культуры, а также развитию этнической, культурной, религиозной самобытности всех коренных народов и национальных меньшинств Украины».[388]Наиболее существенным моментом, вызывавшим трения между Меджлисом и украинскими властями, была проблема предоставления гражданства большому числу крымских татар, вернувшихся после 1991 года. Как уже было сказано, украинским законодательством предусматривалась довольно сложная система обретения гражданства, затруднявшая путь к нему для большого числа крымских татар. Это вызывало многочисленные нарекания со стороны международных наблюдателей, а так же привело к тому, что Меджлис объявил бойкот выборам в местные советы в 1996 году (заявив, что эта акция не носит антигосударственного характера). Впоследствии процедура получения украинского гражданства крымскими татарами была существенно упрощена, но появились новые предметы разногласий между Киевом и Меджлисом.
В частности, ВС Украины принял новый закон о выборах ВС Крыма, который упразднял квоты для татар в представительном органе полуострова. Попытки организовать противодействие этим решениям со стороны Меджлиса не увенчались успехом (в марте 1998 года Меджлис попытался организовать блокирование железнодорожных путей, но эти действия были пресечены милицией, а против их организаторов возбуждены уголовные дела). Представительный орган татар вынужден был смириться с решениями тех, чьим союзником на протяжении нескольких лет являлся.