From what I recall, Macedonians were considered at least as much barbarian as Greek. Sure they may have originally been Greek, but by the time of Alexander, they had lived on the frontier long enough to not be considered true Greeks.
This is at least partially true.
Amyntas I was the first ruler of an independent Macedon, who conducted foreign relations with other countries in the name of the region of Macedon, namely by vassalizing Macedon to Persia.
However, Amyntas was born of Hellenic blood. His son, Alexander I of Macedon was at least considered Greek enough to participate in the Olympic games. Moreover, he was athletically skilled enough to be successful in the Games.
Herodotus, in the Histories, paints the Macedonians as true Hellenes, several times tracing common ancestries of Athenian and Macedonian notables.
Of course, the independently-spirited Macedonians, at least by the time of Alexander III of Macedon (aka Alexander the Greek), had grown tiresome of the several generations of Athenian influence into Macedonian politics. By this time enough hostility had been built that the Greeks, by recognizing their common bonds to Macedon, probably saw them as only slightly better than the Barbarians. And Macedon had little love lost for Athens, as well.
Alexander decided the issue, at least for a little while.