Image loses clarity when it is put over a black background

Question

The original image I do have is the one on the top of this screenshot, I would like it to have a black background. The problem as you can see below is the loss of clarity whenever it has a dark background.

Long story: I need that image to appear as a tile of a menu in a website (http://www.sharpmix.com/) that has a white background. I guess this is the way to go but I'm not a graphics designer at all, any ideas are welcome.

EDIT

Thanks everyone, I've ended up with this:

Answer 1

I'm guessing you used the magic wand tool to select the white background with tolerance set at 32 and anti-aliasing on. If I do that, I get the same result.

Instead, set the tolerance to 1 and turn off anti-alias:

Here's a comparison of the difference:

Zoomed in for better detail:

Answer 2

It's normal. When you make the background dark gray, you decrease the contrast of your image. Maybe you should INVERT it:

Inverting it changes the colors. Playing with blending modes you can get this:

It really depends on what effect you are looking for.