No comentas más de tu proyecto (supongo lo haces en otro post) pero la elección de las baterías es muy importante. Te recomiendo que tu proyecto primero funcione con corriente de sobra (fuente de poder) y una vez funcionando te concentres en las baterías.
Como ya comentan, es casi seguro que cuando tus motores arranquen provoquen una caida de voltaje en tus baterias (para vencer la inercia necesitan más corriente y el voltaje de las baterías cae repentinamente debido a su resistencia interna) y esto reinice tu arduino, te recomiendo usar baterías separadas para tus motores, solo recuerda conectar las tierras de tus arreglos de baterías en paralelo.
El tipo de batería que elijas, ya sea recargable o no, debe ser de acuerdo a la aplicación que le vas a dar. Una batería de Ni-MH (las más comunes recargables AAA o AA) por sus características químicas da más mah si el consumo de corriente es alto (ideales para los motores) pero si el consumo de corriente es bajo (como el caso de la paca arduino que son unos cuantos miliampers) a la larga te va a dar menos mah. Por eso estas pilas son un desperdicio de dinero para aplicaciones de poco consumo como los controles remoto. Las pilas alcalinas son ideales para aplicaciones que requieren poca corriente durante periodos prolongados de tiempo. Así como para no fallar te recomiendo alimentes el arduino con una batería de 9v y tus motores con un banco de baterías AA que puedes extender tanto como necesites.
No te fies de la capacidad que especifican los fabricantes, el consumo, la temperatura ambiental y el desgaste químico hace variar toda la capacidad, yo como regla uso el doble de capacidad que calculo teóricamente, y a veces falta!
Medir el consumo de corriente en pequeñas magnitudes es toda una ciencia, no conozco las demás ligas que recomiendan pero estas para mi estos artículos son excelentes:
http://www.adafruit.com/blog/2010/10/18/how-much-current/ y
http://www.eevblog.com/2010/01/05/article-ucurrent-precision-current-adapter-for-multimeters/