The sketch you linked to varies the motor power from 0 to 255. Can you confirm that you were looking at the performance when full power was applied?
There will always be some voltage drop across the transistors inside the h-bridge. The lower the voltage that is being controlled, the more significant that drop would be. Can you simply increase the supply voltage to the h-bridge?