Personally, I hate the magic wand tool for selection. It sounds like you're ending up with a bad selection. And I would never select and fill - my own preferences is to select, mask, then fill. Leaves you greater opportunities for corrections and edits. But as
@thebestcpu says, without seeing your image, it's tough to determine what will work best.
Other than pen tool, I'll sometimes head to quick selection tool:. Here's a simple piece of line art:
I want to remove the white area inside the pyramid. Magic Wand tool would work on something simple, although my preference is quick mask.
I chose the interior portion, apply mask, invert, and now pyramid is transparent:
But what you might get, with a loose selection, is some of the pixels left over, ie a white fringe:
You can now click on the mask, go to Filter - Other - Minimum and play with the pixel radius to reduce the white fringe. Make sure preview is checked:
Now you're ready to add color to the transparent areas with a fill layer underneath:
This is only one example = Photoshop gives you many different ways to do things. It's very dependent on your image, it's complexity, and what you want the finished piece to look like.
*Edited for type correction
- Jeff