The online Merriam-Webster defines loanword as
a word taken from another language and at least partly naturalized
So, yes, any word that enters a language from another, irrespective of what the roots of that word happen to be, is a loanword. The question becomes clearer when considering that Modern Greek is not Ancient Greek. You could even consider all Ancient Greek words found in Modern Greek to be loanwords (although that might be taking it a bit too far and is likely to get you lynched in the streets of Athens). But let's put that aside and accept that Modern Greek is a direct descendant of Ancient Greek so any words that have survived the journey can be considered autochthonous. Even so, as you correctly point out, τηλέφωνο is not one of them.
To give another example, the word for internet in Italian is, surprisingly enough, internet. That's a word that was created from Latin roots. Would you not consider it a loanword in Italian? It came straight from English. That it happened to have been created using the roots of one of the Languages that Italian is derived from is not relevant and doesn't change the fact that it came into Italian from another language.
Finally, since you ask about native Greeks, I can give you the opinion of one. Sadly, Greeks tend to be very chauvinistic about their language and often put national pride above linguistic analyses. I would bet that your average Greek would indeed consider that word Greek and not a loanword at all. That, however, does not mean that said Greek would be correct to do so. I am a native speaker of Greek and I, personally, would consider it a loanword for the reasons stated above.