I took a look at your logo. Unfortunately there isn’t going to be a quick way to accomplish what you want. The issue is the anti-aliased edges. You can use the color replacer and the paint brush to accomplish your goals.
You will need to replace several shades of gray using the replacer, one shade at a time, and then use the paint brush to clean up any errant shades of gray.
You can start by selecting the color replacer and the replacing the solid black pixels with your desired color. Then switch to the paint brush.
Then zoom in on the pixels which did not get replaced. With your color in the foreground materials palette, click on the foreground patch, which will bring up the Material dialog box.
Mouse over the small circle within the square gradient (inside the circular spectrum gradient). Then left click and drag straight down (just a little) until you have a tinted (lighter) version of your color.
Accept that color by clicking ok on the Material dialog box. Next using the paint brush set to 1 pixel, paint over the errant pixels which match the shade of gray you matched with your tinted version of your color. Repeat this process for each shade of gray within the errant pixels which were not replaced when you replaced the solid black.
NOTE: You can also use the color replacer instead of the paint brush.
The process is to replace the solid black first. Then create tints of your color and replace (with the paint brush or color replacer) the various tints of grey within the anti-aliased edges with your tints of the color you are using.
Another way is to recreate the logo using the desired color(s), which would probably be the best way.
Here is a quick example. I did not take the time to replace all the shades in the anti-aliased edges. To make the edges smoother, you would need to replace all the anti-aliased pixels. Be sure to try and match the tone or tint. If the anti-aliased color is darker (a tone) then select a darker tone of your color. Conversely, if the anti-aliased color is lighter (a tint) then select a lighter version of your color.
In this example, I converted the logo to a layer, removed the background and saved the image as a .png.
mike