From your link:
A 3-cell AA battery box is included, however this makes the motors very underpowered so we recommend using a 4-cell box for alkaline batteries, or 5-cell for rechargeables
So, using 4 cells results in the motors only being underpowered, as opposed to very underpowered.
Are your batteries fully charged? Reputable manufacturer, not some crap from China, made 12 years ago and sitting around waiting for a sucker (I meant buyer) to come along?
That 9V battery needs to be put back in the smoke detector, too. Use the 4AAs to power the Arduino and get a real battery to power the robot.