The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem