Digital replacement for Rotary Capasitor based fan speed controller
Spontaneous triac triggering is often caused by a sharp rise in dv/dt or di/dt, both of which are strongly associated with inductive loads (such as the motor which you are attempting to control). The snubber you have with R1 and C2 should help with this but improper selection of values can easily nullify this effect. Snubberless triacs are made which do not operate in the 4th quadrant and have high tolerance for high dv/dt and di/dt characteristics.

Here's a good example

There are also many application notes on the subject as random triggering is a common problem with triacs when attempting to control heavily inductive loads. 

This is long AND contains almost all information you could want when it comes to triacs

Additionally I agree with @Russel McMahon in that the resistor R2 should not be shared between the triacs, you should add a second resistor of the same value in parallel which feeds the second triac. Attempt to isolate the triacs as much as possible from each other, with no shared components, only shared power supply and load.