Have you tried a regular H-Bridge? Also you cannot have both USB and battery plugged into the arduino together.
Wow - that diagram is confusing. Do you really have ground and 12 volts going to each motor terminal as it appears ? I can't tell from the diagram which contacts on the relays are switching what. Can you post a more conventional circuit diagram ?As has been suggested an H bridge (Google for it) would be the normal way to control motors using an Arduino. There is nothing wrong with using relays but they are on/off devices. An H bridge (motor shield) would allow speed control of the motors which, is nothing else, allows you to soft start them which can be kinder than starting them at full power each time.
I dont even know how to write a program to do any of this, let alone soft start a motor, lol =(