I hadn’t until now written on the issue, but I think now is the time.
Before writing, I read carefully the related Wikipedia article, in order not to write anything obviously wrong (and, of course, always keeping in mind that Wikipedia is no authoritative historical source, just «the sum of the opinion of strangers with no credibility», as Scott Adams of Dilbert fame says).
This country has had this or similar names since 1946; before that it was called Southern Serbia. Since 1993 it uses the name «Republic of Macedonia» internally and «Former Yugoslav Republic of Macedonia (FYROM)» in international bodies. Athens doesn’t like this name because it still includes the term «Macedonia» and because the name is too long, so it’s easier to drop the rest and just call it «Macedonia». Skopje on the other hand does not like the name FYROM because it includes the term «Former Yugoslav Republic» and they are apparently worried about Serb Nationalists having territorial claims. However, in my opinion, since the independence of Kosovo, this argument should no longer be vaild. Furthermore, this is a funny argument from a country with territorial claims itself…
Greece recognized FYROM in 1995 and promised to not block its entry into international bodies as long as the name FYROM was used, which was not the case in the country’s NATO application.
Several names have been proposed by each side and rejected by the other. The UN has proposed (among others) «New Macedonia», «Upper Macedonia», «Slavo-Macedonia», while Greece has proposed «Vardar Republic» or «Republic of Skopje». In the meantime, 77% of the people of FYROM want to keep only the constitutional name («Republic of Macedonia»), while 95% of the Greeks agree with the veto posed by Greece in NATO. Also, as of 09/2007 118 countries have recognized FYROM by its constitutional name. Especially the USA are very openly supporting the FYROM position and pressuring Greece to accept it, precluding that one side is right and the other wrong.
In the last few years, Greece has softened its stance from «no reference to the term Macedonia» to a «double name solution: one internally and one externally», which seems to me what exists today. Instead, FYROM suggests the name «Republic of Macedonia» by everyone except Greece, which can use some composite name. From the Nimetz proposal, Greece seemed more likely to accept the name «New Macedonia», which was rejected by FYROM.
Meanwhile, expansionist aspirations by FYROM nationalists, which include the greek region of Macedonia and part of south-eastern Bulgaria called Pirin, certainly don’t help resolve the issue. A map of these aspirations can be found under the Wikipedia article «United Macedonia». FYROM’s prime minister was photographed in front of such a map on 10/02/2008. The video below shows this map on the wall of FYROM schools, and FYROM school children claiming that their country actually does expand until several cities deep into Greece, while FYROM’s Foreign Minister, when asked about it by a Greek reporter, does NOT condemn this: