I do not know why "They study at private school" was incorrect.
You're missing the an article, either an "a" or "the." In this context, it would make more sense to say "They study at [a] private school" instead of "They study at [the] private school."
Is 'colégio' ever used for 'college'? Or is it just universidade and faculdade and colégio means simply school?
Yes, college is related to university. We say colégio to refer to private schools, but they are also called just 'escola' too, or "escola particular"