He is perfect=Είναι τέλειος. She is perfect=Είναι τέλεια. Adjectives are gender dependent. ;)
when does "τέλειο" mean "perfect" and when does it mean "great"? I've seen it used in different phrases to mean both, and I got marked wrong for translating it as "great" here.
Generally "τέλειο" means "perfect". In cases such as "That's great!" you'd use "τέλειο" again because it's the best available option, because every other just means "big" or "important". Compare the examples given here http://www.wordreference.com/gren/%CF%84%CE%AD%CE%BB%CE%B5%CE%B9%CE%BF and here http://www.wordreference.com/engr/great.
If you search for great AND τέλεια there are 5 results returned; have a look at the comments there too. I cannot say I agree with all of them, but I think they will give you a better understanding of how the terms are related. :)