Yeap, use pliers to remove them. New fans should come with screws, so you can use those if the mounting holes are large enough. If not, just reuse the black plastic bits.
If you can't get a good hold of the black plastic bits with needlenose pliers, a good alternative is just use your fingernails to pinch them. Helps if you let your fingernails grow out a little.
If you do let them grow and pich them, don't expect a perfect manicure later.
If you just can't remove them either way, you can always just cut them off, and enlarge the mounting holes later (drills are usefull for that). Haven't seen cases where the mounting hole's not large enough.
Just thought that you might have a design I used to have on an old case. If its like what I think it is, all you need is to reach inside the case, and there should be another black piece of plastic on the other side of the case, on the fan (in the middle of the fan, near the mounting hole. NOT the motor). Just pull on that, and it should come straight out. Remove all 4, and you've got your fan out.
They replaced those with screws because its alot easier to install and remove. I'd suggest you do the same.