The question was raised by the Macedonia deputy Andrej Zernovski.
Papandreou said the problem was complicated but he hinted that a solution to the 18-year-long problem could be reached soon.
"It's time to make a step forward," Papandreou said in a response to former Greek former foreign minister Dora Bakoyannis, who asked Papandreou to explain upon what he based his optimism.
Papandreou reaffirmed Greece’s stances for a mutually acceptable solution that would include one compound name with a geographic qualifier for Macedonia for use by everyone. That would distinguish the country from the Greek province that is also called Macedonia.
“Greece today is redoubling its effort” to promote good neighborly relations and the prospect of EU membership for the Western Balkans, Papandreou said during his speech.
He mentioned the recent Greek initiative dubbed Agenda 2014 that envisages EU entry of all the countries from the region by that year.
However, Athens previously said that it will help Skopje in its EU entry bid only after a name settlement is reached.
In an interview for the local Kanal 5 TV on Monday, Macedonian President Georgi Ivanov also hinted possible progress in the name talks.
He said that he can not reveal specific details about the ongoing initiatives and talks “at a time when there is finally a possibility for some progress”.
Athens insists that Skopje’s formal name, Republic of Macedonia, implies territorial claims towards its own northern province, also called Macedonia.
In December Greece prevented the EU from extending a date for the start of Macedonia’s accession talks with the Union. In 2008, Athens also blocked Skopje’s NATO entry over the same issue.
Athens has not yet responded to a Macedonian invitation for the two countries' foreign ministers to meet at the sidelines of the conference on Afghanistan's future that kicks off Wednesday in London.
Ever since Macedonia gained independence in 1991, its name has been the subject of a bitter dispute with southern neighbor, Greece.
The longstanding mediator between Athens and Skopje, Matthew Nimetz, rarely reveals his feelings – but admits regret that the name ‘New Macedonia’ didn’t stick.
Placing the statue of Alexander the Great in the centre of Skopje is an unintentional allegory for the end of transition in Macedonia.
The continued blockade of Macedonia’s NATO hopes - which we’re seeing once again at the Chicago summit - shows the West still prefers the principle of solidarity to obedience to international law.