Hey, Adam! Yes, whoever told you that is correct. Because here, the word o isn’t being used as a simple definite article (as the English word the). It’s actually a demonstrative pronoun and, for this reason, it can’t be left out of the sentence. You can confirm this by replacing it with aquilo (another demonstrative pronoun) - the sentence will continue making perfect sense and the function of o will be made more obvious:
Não é o que fizemos, é o que não fizemos. = Não é aquilo que fizemos, é aquilo que não fizemos. (It’s not the things we did do, it’s the things we didn’t do.)
Your initial translation would mean something a bit different:
Não é que fizemos, é que não fizemos. → It’s not that we did it, it’s that we didn’t do it.