Wait what?! Which Furnace are you using? I know exactly what happens but I cant believe this Issue exists in Vanilla.
If it is the vanilla furnace, can you smelt a Wooden Log into Charcoal and then smelt a piece of Coal Ore and see if the same thing happens because Coal and Charcoal share the same metadata?