In Tokyo I would suggest the art store Nadiff in Harajuku for cds. I would also check out Studio80 in Kamata for live events. I was able to see *0, Koji Asano and i.d. there last April. It's tiny but cheap by Tokyo standards (1500 yen w/ 1 drink). They have a website. Also check out the ICC in Shinjuku for interesting new media art.