I would ask these ways:
1) 倖田來未のCDを探してるんですが…
koda kumi no cd o sagashiteru n desu ga.
i'm looking for koda kumi's cd's, (but i can't find it. can you help me?)
2) 倖田來未の新しいCDを探してるんですが…
koda kumi no atarashii cd o sagashiteru n desu ga.
i'm looking for koda kumi's new cd, (but i can't find it. can you help me?)
3) 倖田來未のフリーキーというCDをさがしてるんですが…
koda kumi no "freaky" to iu cd o sagashiteru n desu ga.
i'm looking koda kumi's cd called "freaky," (but i can't find it. can you help me?)
i think these are the most polite and natural ways to ask.
the shop clerk will take you right there.
but for ease, the ________はどこですか?construction won't fail you!
marky
ps. keep in mind, if you're looking for a non-japanese artist, you'll be best off if you use a katakana-ized version of the name.