I think you are thinking of Toraya which, according to sidewalk.com, sells "Japanese Confections, Tea Shop, Light Lunches."
17 E. 71st St (bet. 5th & Madison)
Or, maybe you saw the spot on Martha Stewart Living on Wagashi? The info from the website (link below) is:
Kamakura Minamoto Kitchoan
Swiss Center, Ground Floor
608 Fifth Avenue
New York, NY 10020
If the link doesn't work (you may have to log in, or it may be out of date by the time you read this) the episode aired March 23, 2000, look for the "Japanese Sweets with Sara" spot in the Television section. Or, try http://www.kitchoan.com/