Правильно: в городе Нью-Йорке, в штате Нью-Йорк. Топонимы обычно не склоняются в сочетании с родовым словом штат. А вот в сочетании с родовым словом город топоним склоняется, если он русского, славянского происхождения или представляет собой (как в рассматриваемом примере) давно заимствованное и освоенное наименование. Такие названия можно считать исключениями из процитированного Вами правила (статья дополнена этим примечанием).

Скорее всего, это связано с тем, что в русском языке не существует употребляющихся самостоятельно слов Тель, Авив, Буэнос, Айрес, Анджелес и т. д. Согласно нормам русской орфографии раздельно пишутся только составные географические названия, представляющие собой сочетание существительного с предшествующим прилагательным или числительным (Нижний Новгород, Ясная Поляна, Царское Село) или включающие в свой состав такое сочетание (мыс Доброй Надежды). Конечно, в названиях Нью-Йорк, Буэнос-Айрес первая часть тоже является прилагательным (нью – новый, буэнос – добрых), но по-русски они как прилагательные не воспринимаются.

Подобные сложные наименования, как правило, остаются несклоняемыми. Только некоторые (наиболее известные) топонимы такого типа подчиняются общему правилу: в пишущихся через дефис иноязычных топонимах склоняется только последний компонент. Вот примеры из «Словаря собственных имен русского языка» Ф. Л. Агеенко:

Аньер-сюр-Сен, Аньер-сюр-Сена [сэ] (гор., Франция)

Витри-сюр-Сен [сэ], нескл. (гор., Франция)

Шалон-сюр-Сон, нескл. (гор., Франция)

Камаре-сюр-Мер [рэ, мэ], нескл. (гор., Франция)

Рошфор-сюр-Мер [мэ], нескл. (Рошфор) (гор., Франция)

Трувиль-сюр-Мер, Трувиль-сюр-Мера [мэ] (Трувиль) (гор., Франция)

Конде-сюр-Нуаро [дэ], нескл. (Конде) (гор., Франция)

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