The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem (with appendix and software)