夢時代購物中心
http://www.dreamall.com.tw/dreamMall/index.asp
It's basically Taiwan's largest shopping mall. You can't miss it, it's so massive (it has a ferris wheel on top). All the taxi drivers know. Anyways, there are 2 CD stores that I know of in there. The one with newer stuff is on the bottom floor with all the food court stuff. Just take the escalator down and it should be right behind it. However, if you're looking for the used one, just go up the escalators (I'm not sure what floor). You should see it sooner or later as you go up the floors because it's right in from of the escalators.