There's an excellent Mexican restaurant at the Kokubunji (国分寺駅) station on the southside. From Shinjuku, take the Chuo Line toward Takao (高尾). It was about 2000 yen for a set meal, but OMG it was heaven. The chef personally came out and told us about each dish because I had told the waitress that I'm American and just love Mexican food.
One dish had a cocoa mole sauce.
Here's the address for anyone interested:
Viva Japanesque
国分寺市南町3-28-8
Tel: 042-324-1746
They can speak English, Japanese, and possibly Spanish.
Anyone wishing to go there one evening please contact me and I'll go too!