Where does this logical argument against creatio ex nihilo break down?

[Gorgias]

I said that creation is the act of bring potential to actual.

In classical philosophical thought, this is true. However, it’s necessary to ask what ‘creation’ means in this context. Aristotle is talking about the creation of something from some other thing, such that the newly ‘created’ thing exists potentially in what comes before.

Therefore, a chair exists potentially in a tree.

In this sense, Aristotle is correct: in the universe, nothing can come into being without pre-existing material from which it is formed. This is logical, and God does not contradict this.

However, before any material in the universe exists, there is no material from which to draw potentiality. It would be illogical to suggest that it does. Therefore, God does not contradict this logical assertion, either. Rather, He creates the universe ‘ex nihilo’, thus paving the way for subsequent physical ‘coming into being’ to take place in a logical, consistent manner.

The act of bringing no potential to actual is what I deemed illogical

Within the framework of the universe, you are correct. Outside that framework, you are invalidly extrapolating. Keep in mind that, to Aristotle, the universe was eternal, and therefore, for him, there could be no exceptions to his argument for potentiality giving way to actuality. However, in the Judeo-Christian context, in which God creates as the first cause, that assumption must give way.