Have there been cases where a sovereign Communist government ran in an open and fair multi-party election and conceded a loss?
The reason for the sovereign qualifier is simple. If, for example, the Indian state of Kerala has a Communist government, it stands to reason that, as part of India, it could not (assuming it even wanted to) cancel elections or manipulate them overmuch - the federal Indian government would not let it.
Also, the Communist government in my question need not have been elected into power, it just needs to have allowed free elections once it had power.
edit: The notion of agency, or free choice, in allowing elections is important too. Eastern Europe in 89-90 was imploding, people were fleeing through newly opened borders and Gorbachev refused military backing. People like Honecker deserve praise for not ordering their troops to shoot (with uncertain outcomes, cf Romania), but it's not so much that they believed in democracy, it's that they had run out of all other options.
edit #2: for the purposes of the question, a Communist party is one which calls itself Communist or whose party manifesto explicitly indicates its adherence to Marxist/Leninist principles.