You can't go wrong with Super Potato. It's in one of the back streets so it might be a bit harder to find, but once you do it's totally worth it. They even have a throne made out of Famicom carts there, and a whole floor dedicated to old-school arcade games. Here's one map I dug up with the store's location:
http://map.yahoo.co.jp/pl?lat=35.41....-2&pref=&kind=
I actually found it "accidentally" when I was walking through one of the back streets, and at some point I heard the NES theme from Legend of Zelda playing through some speakers - I followed the tune and it led me to Super Potato =)