@MetalDan Not really, you have done the first thing I would have suggested (batteries in the fobs). The fact it is doing the same thing with both indicates as you say something to do with the car or at the very least not the fobs. As for car battery - probably not an issue in this case... mine had no trouble with locking/unlocking (first time each time) until one day the car was just dead (not surprising when the old one read 7.6V or something).
One thing I am wondering about... during the 10-15 tries... do the lights on the car flash at all? Just wondering - as them flashing would indicate it receiving the signal and trying to do as commanded - indicating maybe an issue with the locks/actuator (or their driver) part of the system. No flashing the signal probably isn't being received - I am pretty sure if the system can't arm for whatever reason the lights still flash (just different to usual).
Dazzler has already covered RF interference - there are a few reports of such occurring.
Of course a bad aerial connection to the BCM could also show similar symptoms. The aerial runs from the BCM (which is approx. behind the coin tray/12V socket, etc. - e.g. lower part - of the central fascia) along the dash somewhere - don't know that you can check it much though.
