Those 9 volt batteries have very little drive capability, use a wall-wart.
You need a .1UF capacitor on the input to GND of the regulator for to prevent possible oscillating.
Do you have the ground of the I.C. going to the Arduino GND?
Edit
What do you measure across the battery terminals?
Also, you do realize that motor is geared down 64:1 do you?
.