Huh. Usually, the parking brake setup on drum brakes will hold better downhill, rather than uphill.
Without seeing what they look like, the only things I could suggest is make sure the parking brake lever inside the drums is free and applying pressure equally to both shoes. Also, add a dab of white grease (lithium greas) to each of the spots where the brake shoes come in contact with the backing plate. Take care not to get any on the friction linings, of course!
You said the cables are new? It might take some time to stretch them a bit before they will apply good, even pressure. Try tightening it just a bit to see if that helps. And check to see that both rear cables are getting even pressure from the intermediate cable. To do that, set the brake and tug on both cables individually. They should have the same give.
