It looks like you have some coincident geometry, but it's hard to tell what's causing it. It's quite possible that you have two copies of the same thing there, one of which is getting the material you want, and the other is covering it up. Right-click and drag on that model to make sure there's not another one underneath it.
Make sure that you're doing your selection in wireframe mode (not shaded), so that you're certain you're getting all the vertices. Keep in mind that you'll have to DEselect any vertices on the opposite side of the model, that you don't want to use that material.
I hope this helps!