Ruia, your problem is your thinking with the computer rather than your creativity. Grab a pen, go to a cafe, grab a napkin and draw crazy ideas. The more the merrier. Once you have an idea then refine it in pen or pencil and show it to some other creatives and get feedback. Then go to the computer and you will look for the fonts that fit your design.

One other thing. Research! Visit competive sites even local retail stores. See what they are doing right and wrong. Hang in there and post some of your ideas.

As much as I'll probably take heat for this, I will say that the specific font isn't that important. You're over-thinking the details before your thinking about the big picture.

What are the goals of the new logo? What's wrong with the old one? What types of applications will the logo be used on? What's the target demographic? What's the competition look like? Etc, etc.

Don't worry about a specific typeface at this stage...that will come naturally later on.

Draw, sketch, draw, sketch, make notes, experiment with type faces on your computer and print out the results. Keep challenging your decisions. Look at things by the dawn's ugly light. Draw, sketch, draw, sketch, ad infinitum. Guys who hit home runs have been swinging bats at fast balls for more than a semester.

I highly recommend Erik Spiekermann's Stop Stealing Sheep & Find Out How Type Works, it's a good basic tutorial on type styles and how/when/why to use different fonts. Ask Santa for a copy!

<font class="dontLookLikeCrap">I agree with Darrel: you haven't yet asked yourself what this logo will BE, and that's the first step, before 'what will it look like?' The second follows naturally from the first.</font>