В 1989 году он представил в Канне "Время цыган", где эта же самобытность повернулась новой гранью. Режиссер вырос по соседству с цыганской общиной и получил от цыган первые сигналы дружбы и свободы.
Вскоре после премьеры этой картины Кустурица приехал в Россию в жюри Московского фестиваля. К этому времени мы уже пережили шок деидеологизации. В нашей столице побывали еще недавно предаваемые проклятиям Милош Форман и Душан (страшно сказать!) Макавеев — знаменитый югославский "антисоветчик и порнограф".
"Время цыган" было не столь свежо и блистательно, как предыдущие ленты Кустурицы, но все же фильм был очень хорош. Несколько затянут, но не скучен. Чуть-чуть эксплуатировал экзотику и эротику — "на потребу", но "в меру".
Кризисной работой стали "Сны Аризоны" — попытка полуголливудского фильма. Сны были изумительно романтичными — с летающими рыбами и узкоглазыми эскимосами, с дивными арктическими пейзажами. А реальность Аризоны, населенная тройкой голливудских чудаков (Фэй Данауэй — Джонни Депп — Джерри Льюис) вымученно-сюрреалистична.
Кустурица вымучивал этот фильм годами — драматургически и производственно. Он анонсировался то одним, то другим большим фестивалем, но так нигде и не появлялся. Наконец, он все же был представлен в 1993 году в Берлине, где Кустурица (о, счастливчик!) опять сорвал спецприз. Жюри оценило очень красивую (ставшую шлягером) музыку Бреговича, стерильную чистоту авторских намерений и простило впервые прокравшийся в мир режиссера маньеризм.
Однако провал "Снов Аризоны" было уже невозможно скрыть. Картина оказалась на периферии американского проката, коммерческие успехи были на нуле и в Европе. Дорогой проект, стоивший массу хлопот и нервов французским продюсерам, подтвердил мнение о том, что даже лучшие восточноевропейские режиссеры отделены от западного кинопроизводства фатализмом восточной (славянской) ментальности. Кустурица, раньше других вырвавшийся из железных объятий идеологии, забил один из первых гвоздей в крышку гроба с иллюзиями всеобщего кинематографического братства.
Поворотным пунктом в биографии режиссера стал фильм "Подполье" (1995). Именно в это время миф Кустурицы достиг своего апогея в России. Еще до премьеры "Подполья" в Канне фаны сделали ему поистине мифотворческий
На Западе же за победой последовали неприятности. Как и в случае с "Аризоной", Кустурица долго занимался перемонтажом, прежде чем выпустить новый вариант во Франции. Тон появившихся рецензий был настолько убийственным, что Кустурица заявил о своем уходе из кино. Он почувствовал себя жертвой политической анафемы. Травлю развязали левые французские философы и критики образца 68-го года, которые сочли "Подполье" политически некорректной и просербской картиной.