Three other stores besides the ones that Brett suggested that I really like are Kamoshika in Takadanobaba (one of my favorite stores, though still very traditional... GREAT alpine tents! They also make their own lightweight packs. They really know their stuff there.), the mountain climbing head ICI store in Shin-Ookubo (station after Shinjuku, on the Yamanote Line), and Nippin, in Akihabara (they make very strong, single-wall mountaineering tents designed by Reinhold Messner). There is also a small outdoor backpacking store (I keep forgetting the name) on the south side of Kichijoji, where they have a really unusual assortment of equipment that often you cannot find anywhere else, including some really nostalgic mountaineering items from 20 to 30 years ago.
Brett's suggestion for the OD Box in Okachimachi is spot on; I think it is the best store in Japan for UL gear. Sakaiya Sports in Jimbocho is the best all around store in Japan for the newest international outdoor gear, I think, though they're often out of popular sizes for shoes in their shoe branch store. If you go to the Mont Bell head store in Ebisu, the second floor (that many people don't know about) is a MontBell outlet store with some great deals on older items. One thing about Japanese outdoor stores is the availabilty of great brands that most Americans don't know about, like Eider from France (sort of like the Patagonia of France), Millet of France, Fjellraven and Haglofs of Sweden, Norrona of Norway, Camp and Mello's of Italy, and Artiach of Spain (they make a wonderful, thin, very light (170 g, 185 cm x 55 cm) closed cell sleeping mat called the "Light Plus" that is just as comfortable as a Ridgerest).