Using Darlingtons in an emitter-follower is, um, quite wasteful - the output can never approach the supply rails because of the doubled Vbe drop. They work much better when acting as common-emitter, ie with the NPN at the bottom and with inverted drive for the PNP at the top.
Better yet, use FETs.
Worse still, you are running it I think in fast-decay mode (the whole power supply is expressed across the motor inductance via the diodes while the transistors are off). If you want it to run at low power, you probably want slow-decay mode. Requires some rewiring.
Anyway, I think what you're finding is that the motor has friction and will not turn at half power. You could set the PID limits to (150,255) and put a special case in there so that you write zero to the motor when the PID output is at its minimum.