A few things to look for:
-Make absolutely sure the wheel is centered in tthe fork. Hold the bike up with both wheels on the ground. Loosen the QR, and tighten it with the axles all the way in the fork. If the rim isn't centered in the fork when both axles are all teh way in, your wheel isn't dished properly, which means the pads are going to contact at odd angles. Chances are, the wheel is fine, but the wheel has to be right to get the brakes right. If it's not, part of the feel of the brakes being applied will be the brakes sliding up and down on the rim as the wheel flexes a little bit. That'll screw things up, and keep the pads from properly grabbing the rim.
-Look at the pads when the brake is fully applied. Are the posts perpendicular to the rim? There are washers on the post that look like a half a ball, and a cup. They're there so you can adjust the pads to a certain angle. They shoud both be at the same angle, and they should both be perpendicular to the rim when fully applied. If you have to re-adjust the pads, do yourself a favor, and disengage the springs on teh side of the brake, so they're not pressing away from the rim when you're trying to get them lined up.
Hold the caliper to the wheel with one hand, and have something like a business card, a credit card, or something else under the back part of the pad while you're tightening it down. This is called "Toe In." The idea is to have the front of the pad contact first, and the rest of the pad will squeeze down when there's more pressure on the brake. It cuts down on squealing pads, and helps you modulate better. It's not some advanced technique, it's part of proper brake alignment.
-Make sure the pads are contacting the middle of the rim, and not hanging off the edge towards the center of the wheel, or rubbing the tire.
-Be sure (you said you're sure, but I'm repeating it) that pads and rims are completely clean. If you're nto 100% sure, wipe them down with alcohol, adn acetone. The alcohol shoudl dissolve any greasy stuff, the acetone shoudl dissolve any rubber residue.
-Watch the brake when you're applying it. Both arms shoud move more or less the same amount while it's being applied, and move more or less the same distance to the rim. If they're not, there are screws on the side of each brake arm. Tighter screw, tighter spring. If one arm is moving more, it has more tension than the other brake arm, and you should either loosen that arm, or tighten the other one. Soemtimes it takes some tinkering to get them even, but it helps the system to stay balanced. If one arm is too tight, and is way out, you have to pull the cable far enough to get it even with the other pad, and then more to apply the brake. If both pads are even, you can take slack out of the brake cable, and you'll have more tension you can apply to the brake.
-Check the ferrules at each end of the cable housing. Each end should be properly seated in either the barrel adjuster on the brake lever, or the "noodle" on the brakes. Watch the ferrules while you're braking... they shouldn't move very much at all. But it's possible when you're braking, what you're doing is just moving the housing ferrule aorund, rather than putting the power to the brakes.
-Check for tight bends in the cable housing. Tight bends make for more resistance pulling the cable, so half the energy you think you're using ends up going to just making the cable move. If you're feeling ambitious, you can remove the cable, and make sure the ends of the housing aren't pinching the cable. That's another possible source of friction.
-Lastly... If the brake pads and rim surface are clean, if the brake arms and pads are aligned, if the cable is sliding smoothly, look at the fork while you're braking. The last thing I can think of is that the fork is flexing when you brake. Watch the bolts that attach the brakes to the fork. If you see them move away from teh wheel, the fork is flexing. If that's the case, look into buying a brake booster. Salsa is the best buy for the money, but even a $10 tektro brake booster can help.
I knwo this is a lot of information, and that you're a new guy, but don't worry... just go through everything one step at a time. There's a lot more to brakes than a lot of people realize, but none of it is really all that complicated.
