Seems like at worst a classic case of nat bar nat and therefore would be allowed bidieved.
Actually, to go ahead and mix the potatoes into the cheese salad would be considered l'catchilah, not b'dieved, and would therefore not be allowed according to your reasoning. However, in this case it would ultimately be allowed because the oven was not a ben yomo.
(I'll also assume that the potato was baked in an aluminum foil or such, and not in a fleishige pan, as that would change the question)