Yes, it does sound like the dimmer is affecting the zero crossing detection. Try swapping it for a solid state relay with a MOSFET output stage.
This has nothing with mosfet or non mosfet SSR. You can get SSRs either with zero crossing or without it (random turn-on).
http://www.crydom.com/en/tech/newsletters/solid%20statements%20-%20ssrs%20switching%20types.pdfHowever, this most likely is something else. Zero crossing could not allow to turn them on. Exactly opposite to being unable to switch off.
IMO this is because those SSRs lack any snubber in them, and the dimmer outputs high voltage spikes because of inferior or faulty filter (like dead X class safety rated capacitor, happens quiet often in dimmers). Usually there is some kind of coil (though cable inductance can be enough for causing the problem too) to reduce interference caused. This inductance can cause high voltage inductive kickback. And phototriac optocouplers (in SSR), especially types without zero crossing, are very easy to trip if exceeding the peak voltage. I've seen this when repairing dimmers. X class cap in the snubber fails, and then dimmer just cannot turn off after setting it on, even if phototriac optocoupler is not faulty, it just gets tripped on by the inductive kickback.
EDIT: Which particular SSR model? In the datasheet there are SSRs with or without a zero crossing, with or without a snubber. The other question is if those SSRs are genuine or "china special" from ebay/shady place.