Definitely add the capacitor. 470uF is an absolute minimum and if your motors have low inductance them you might well want a bigger value. Lack of the capacitor in conjunction with inductive spikes from the motor (at 500Hz with Arduino PWM) could easily have damaged several things.
It sounds like you've blown up one of the output transistors - I suggest putting them in a transistor tester and making sure nothing has a collector/emitter short. Worst case, you need to replace about $3 of silicon, but try to figure out why it blew up or it will happen again.
PS opto-isolators between your Arduino and motor driver are a very good idea. They're very cheap and will save you from blowing up a $10+ microcontroller and/or all the expensive stuff it might be connected to (your PC?).
I see you've met our troll.