It sounds like your laptop can't supply enough current to charge the phone. Most USB devices only want a fraction of an amp of current (e.g. a mouse might draw 0.1 A), so the USB ports on laptops can only supply a little current. Generally a phone or tablet wants 1 A or more to charge efficiently, which most USB ports can't supply.
The cable isn't really the issue. As HasH_BrowN states, cables can be damaged, so it's good to check with another, but in this case the problem is what the cable is plugged into. Ideally, you should use the wall charger that came with the phone.
When you do have to plug it into a lower-current supply like a PC, you can get best results by turning the phone off to charge, so that the phone's not using more power than it's getting from the charger.
For more explanation of why chargers don't always charge, you might like to look at the related questions such as What causes battery to drain faster than it can charge?