I'm assuming the logo is in a raster format (tiff, jpeg, etc)rather than the for more useful and proper vector format (the format in which most professional logos are created). If it does appear to be a vector (generally eps format), you could open in Illustrator and knock out there.
If it's rastere, it's very hard to get a really clean edge when knocking out something, especially if the dpi is rather low. You might try opening the raster in photoshop, upping the resolution dramatically, knocking out what you don't want and then sharpening the edges.
When I've been really stuck with low quality raster logos, I've created paths (selecting the various elements with the magic wand) in Photoshop and the exported those to Illustrator. Then filled in the proper colors. That's the only way I've ever been able to get clean eges that are the strength of vectors.
Using OSX 10.3.9 on a G4