heyHI Duncan - well, there are the Y's Shops close to Shinjuku Ni-Chome (Gyoenmae station), Bic Camera has some Bikes stuff, Cycly Used in the Seibu Station Building (near East Exit), Outdoor Space which is small BMX shop on Meiji Dori and Okubo Dori (Higashi Shinjuku). As for MTB Fixie - nothing in the Shinjuku hood. As I ride fixie I know pretty much any place that would have something like that. If you don't want to roll your own, then you'd be looking at perhaps F.I.G. , Blue Lug or another boutique shop around Tokyo.
im looking for fixie OR mtb
hahaduncan your shop selection/experience will depend a lot on how well you understand and speak Japanese.
Y's Road in Shinjuku
Exit C8 from Shinjuku 3-chome subway station takes you into the B2 level of the BYGS building. Y's store is one floor up. They also have a cyclewear store on the same floor.
If you go by bike, you can wheel your bike into the building, down the escalator, and park it on a hook just inside the store. More secure than strapping it up outside, especially if it's a nice one.
Just over the road, tucked away in a corner, is Y's Custom (a.k.a. Maniac, a.k.a. Joker), which sells more bling stuff, and some of the same stuff.