Thanks for all the help! This goes a long way towards my understanding of the how/whys. The reason for different value caps (And the need for caps) now makes a LOT more sense.
I'm probably going to just start over with the additions mentioned.
@ Docedison: I don't really understand this: " Batteries are a constantly changing impedance/resistance as they become discharged, 100 to 220 uF caps will give you 20 - 30% more battery "life" before they need to be changed out." do the 100 to 220 uF caps go in the same place as the 1000 uF cap recmmended?
Also, does it make sense to run 2 voltage regulators? One for the IC and one for the motors? I figured it would be better to keep them isolated but they really aren't, are they? When I breadboarded the project I was using an UNO with the motors on a VR and the VR got pretty warm.