Stepper motors can not get past 150rpm

Should the two COM connectors be connected to the Arduino ground?

Yes always connect grounds together.