There are H-bridge driver chips that do all the work for you BTW, like the HIP4081, and they let you use all n-channel MOSFETs.
First piece of advice - protection circuitry is required between the Arduino signals and the H-bridge (even a 2k2 resistor in each signal line might be enough).
Second piece - switch the MOSFETs fast, something like a MIC4422 buffer is a good idea to drive that gate capacitance. It can drive upto 9A which is plenty and it takes logic level inputs. Certainly something more like amps than milliamps is necessary or your MOSFETs will spend lots of time in the linear region and overheat/burn. You need lots of ceramic decoupling close to the gate-driver to do this successfully, at least ten times the combined gate capacitance.
Thirdly have suitable delays (hardware or software) so that it is impossible to have both the top and bottom MOSFETs on simultaneously. This situation is called 'shoot through' and causes all sorts of chaos. If you switch in 250ns or so the delay only needs to be a few hundred ns.
There are H-bridge driver chips that do all the work for you BTW, like the HIP4081, and they let you use all n-channel MOSFETs.You should also be aware of the Open Source Motor Controller project http://www.robotpower.com/osmc_info/
Hmm, I think I understand what you are saying. Basically, whenever I want to utilize the other two FET's, make sure I leave suitable time between turning two of them off, allow all current to leave the circuit, before turning the other 2 on? I don't think we're going to be doing running the motors using PWM so the only chance that 'shoot through' will occur is when changing directions, I presume.
Why don't you be a bit more negative, haha!! would love to buy one off the shelve but at ~£20 each they're too expensive. We need to drive 6 motors in forward and reverse, so if I can't get this H Bridge to work, I'll use the relays.
I don't the part number here at the moment, the datasheet is at uni, but we wanted something similar to this:http://www.national.com/ds/DS/DS0026.pdf (which unfortunately is now obsolete).