My rear brake is jamming to the point that only half seems to be moving. With worn blocks I got away with it, but now I have changed the pads I finally need to sort the problem. Could the brakes be in need of a good clean, or could there be a fundamental issue with the brake?
You probably need to grease the pivots. For cantileaver brakes check out this page. For caliper brakes I would just drip a little lube into the pivots. If grease doesn't help you may want to consider taking the bike to your LBS for service/ advice. Adding some grease to your cable housing may help as well.
I had the same problem with mine earlier in the winter when they got filled with salt and road grit from my daily commute; after taking them apart, cleaning the dirt out of any motion points, and lubricating them, they work great. If you don't feel like taking them apart, at least try lubricating them first and that might suffice.