The cables tend to soak up water and road salts. If the parking brake is not used very often, the cables can sieze. Sometimes they will move enough to set the brake but are dragging enough that the return spring does no good at releasing the cable.
You have 2 options open to you at this time.
1. Soak/spray the line with a good rust buster lubricant, such as PB Blaster, and let it set for 24 hours. Then attempt to set the brake and release it repeatedly. You may have to pull the cable undernieth the car to get it to come back the first time. After that just keep working it till it works smoothly.
2. You can replace the cable with a new one.
After you get it free, just remember to use it a little more often to keep it free.