Just connect the GND of one to the GND of the other.
Without a reference point (ie the GND) the voltage levels seen by each Arduino can be any old crap, probably similar to the pins just floating.
When you were using USB the GNDs where connected via the USB cables. With the batteries there is no connection.
Rob