In Manhattan there was a place called the Chinatown Ice Cream Factory. Don't know if it's still there. Their flavors included: Green Tea, Black Tea, Red Bean and Black Bean. They were all really good. I recently bought a half gallon of Japanese green tea ice cream an an Asian grocery store near my house. It tasted like dirt.
And on the subject of Japanese ice cream, there was a website devoted to Japanese oddities (I forget the URL), and they had a section on ice cream. No fruit flavors, but meat, fish and vegetable flavors, like horse meat, potato and spinach.