The Kinokuniya in Rockefeller Center has Ayumi CD's and videos as well as fashion magazines. They used to carry Ayumi's magazine "Ready? Go!" before it was discontinued. The prices are high, though, so save up if you're planning on going there. Sometimes if they have backissues of magazines, they will sell for half price (ex. $8 opposed to a full $16)

Chinatown probably has some bootleg stuff, but I haven't been down there in over 5 years.