Automatic tracing tools can be hit or miss and they're certainly better for when the artwork is well suited for it. It's difficult to offer specific advice without seeing the logo, but logos should typically be manually vectorized (or at the very least, hand tuned after auto tracing). Ideally, logos should be initially created in a vector editing program from the start rather than raster than converting, but that's a different discussion.
To become proficient at vectorizing things, you'll need to get comfortable with the Pen tool and Bézier curves. You can often save yourself a lot of effort by breaking the art down into basic shapes such as rectangles and ellipses. To provide an example of how you should break down the composition, here's the Twitter logo constructed using circles only:
Image courtesy of designshack.net
Admittedly, that's a rather extreme example and you don't need to be that crafty. But the more you break the artwork down into basic shapes, the easier it can be. Anything that remains can be constructed with the Pen tool. It takes some getting used to but with some practice you'll get the hang of it. You can look up videos for guidance or check out Adobe's help docs.