I have stayed at a publicly owned albergue in San Roman de Retorta. It was about 1 km out of town in a beautiful wooded site where some large livestock market used to take place, I think. It's very small, with beds for 10-12 and a little kitchen in the middle of two bedrooms.
When I was there, in 2008, the albergue was newly opened and was designated as "provisional", suggesting that a new (bigger?) one was being constructed. But I haven't seen any news that anything else has opened there. So, by "new", I take it you mean the small place where I stayed. If so, I recommend it highly, it's a beautiful site. The bar in town sells basic food for cooking (pasta, cans of meat/tuna, etc) and will also make you a meal.
Another option between Lugo and Melide is the private casa rural Casa do Ponte. It's about 7 km beyond San Roman. I didn't stay there but ate a good breakfast there.
Buen camino, Laurie