[PaultheS]

Think of it this way:

H1 = first coin was heads
T1 = first coin was tails
H2 = second coin was heads
T2 = second coin was tails

Your question is: What is the probability of (T1 AND H2) OR (H1 AND T2) given (H1 OR H2)?

P(T1H2 OR H1T2 | H1 OR H2) = P((T1H2 OR H1T2) AND (H1 OR H2)) / P(H1 or H2)
= (0.5^2 + 0.5^2) / (0.5 + 0.5 - 0.5^2)
= 0.5 / 0.75
= 2/3

So, as you see, your teacher is correct. The key is that you aren't told which coin is heads, just that at least one of them is.

Of course, if the question were different and you were told that the first coin was heads then the probability that the second is tails would be 1/2, and vice-versa.