Yuriy Boiko arrived in Moscow to hold negotiations with Russia's JSC Gazprom on gas supplies, Ukraine's Prime Minister Viktor Yanukovych said at a Cabinet session, adding that he too may go to Moscow. "The issue is very complicated," he said.
Both Gazprom and Ukraine have said the dispute would not disrupt Russian gas exports to the European Union as in early 2006, when Gazprom cut off supplies to Ukraine over a pricing dispute.
Gazprom's ultimatum on Tuesday came during Ukraine's fiercely contested parliamentary elections in which the reunited Orange Revolution allies made a strong combined showing and looked likely to oust their longtime foe, Yanukovych.
Yanukovych - who was strongly backed by Moscow in the 2004 presidential race, which he lost to pro-Western Viktor Yushchenko - has taken a more neutral stance since then, promising closer integration with Europe. But he is still seen as more Russia-friendly.
While Moscow did not get involved in Sunday's early election, which Yushchenko called with hopes of unseating Yanukovych, the gas ultimatum could reflect a Kremlin attempt to influence Ukrainian politics.
Orange Revolution heroine Yulia Tymoshenko, who stands to be appointed prime minister if her bloc and Yushchenko's party form a majority in parliament, said after the vote that she would seek to negotiate a new gas deal with Russia that would better protect Ukrainian interests.
Gazprom could have put the debt on the back burner to avoid damaging Yanukovych before the vote, analysts said. Now, with the Orange parties on the verge of victory, the Kremlin may have toughened its stance in anticipation of future talks with a Tymoshenko government.
Mykola Azarov, one of Yanukovych's deputies, disputed Gazprom's statement, saying that Ukraine has no outstanding debt to Gazprom, news reports said.
Gazprom's spokesman, Sergei Kupriyanov, said it was not the Ukrainian government but gas consumers in Ukraine who have run up the debt.
"If Azarov is talking about the Ukrainian state, it's true," he told The Associated Press. "But Ukrainian consumers are in debt."
Vadim Chuprun, Ukraine's deputy energy minister, said earlier Wednesday it was not clear what Gazprom's calculation of Ukraine's debt was based upon.
"We need to look into this. The debt is divided into several parts. There are many players on the market and we must find out where this debt is coming from," he said in televised comments. "But if this relates to us - to the state - we will make sense of this immediately."
Chuprun said the country had enough gas in its reserves to ensure uninterrupted transit gas supplies to Europe.
Gazprom's ultimatum raised the specter of a drop in gas supplies as in early 2006, which raised concerns in the European Union about an overreliance on Russian energy. Gazprom supplies a quarter of the gas used by Europe, and the pipelines that cross Ukraine transport most of it.
Tuesday's warning referred specifically to cuts in supplies for Ukrainian users. But, during the previous dispute, Gazprom accused Ukraine of siphoning gas, leading to decreased supplies farther west in Europe.
Despite the assurances from Gazprom and Ukraine that gas flows to Europe would not be interrupted, the new controversy caused some alarm.
The European Commission called for a "speedy settlement" of the issue. The EU's executive body said that Gazprom had informed it of the problem and "committed itself to honor all existing gas supply commitments to European companies, which were informed about intended measures vis-a-vis Ukraine."
Early in 2006, Gazprom nearly doubled the price of gas for Ukraine - from US$50 to US$95 per 1,000 cubic meters. Starting this year, it has increased the price to US$130 - just about half of the US$250 Gazprom charges other European consumers.
The Kremlin has been accused of using the gas price as a political tool to reward its allies and punish Western-leaning countries in the former Soviet space.
But Gazprom has insisted that its intentions are only to bring the price to market levels and stop subsidizing Russia's neighbors.