This is just in 31.13 right?
Nope. I had a problem with stockpiled/unforbidden/untasked/undumped charcoal in .12. The smelter wouldn't accept that it had fuel. Tore it down, built a brand-new smelter, and everything was peachy. For the record, the charcoal was only a few steps away from the original smelter, and the new smelter was built a few steps away in the other direction. It wasn't an issue of sprawl, or haulers claiming the bars, since this was in spring or summer of the fort's first year--the whole place was nothing but a tunnel with a door slapped on it. No z-levels, no multiple stockpiles, no mooks on the other side of the map calling dibs on hauling things.
Good news everyone: I HAVE THE SOLUTION TO THIS PROBLEM (so we can all stop bickering now)
Ok, the problem is with smelters, not charcoal/coke/coal/whatever, and there are two ways it will manifest itself:
1.) Smelters do not recognize bar-based reagents that are on a different Z-level. Period. I tried moving all of my metal bars upstairs once and then found myself unable to make any steel despite having plenty of all the needed materials. Keep your bars stockpile on the same level as your smelters. They can use ore and economic stones from anywhere though, so you can keep your ore stockpile on a different level, but bars must be on the same z-level.
Dunno about the OP, but in my case, it couldn't have been a z-level bug because everything in the fort was still on the same z.
You're right on it being a smelter prob--I built a new smelter, and that workshop didn't give me the "no fuel" line... the original one still did. I went back and forth between the two of them; the new one would take smelting tasks, the old one wouldn't, and there was fuel available to both.
2.) Newly produced coke is unavailable to your smelters. Why? Because if you have a stockpile that accepts bars, then as soon as your coke pops out of the smelter, it gets claimed by your haulers who mosey on down from the break-room to transfer it to the proper stockpile. The problem is that the coke becomes unavailable the moment its "un-filed" status becomes noticed regardless of how long it takes for the dwarves to actually come and get it. This results in the phenomenon that when you're down to your last bar of coke and need to make some more, and set a repeating order to convert your lignite into something useful, the task gets canceled after the first round because there is no "free" coke sitting in a stockpile; it has all been claimed by haulers.
I had charcoal, unforbidden, undumped, and untasked in a stockpile right next to the smelter and the smelter wouldn't acknowledge it. It wasn't a tasking/stockpiling issue.
The smelter would keep trying to use my imported coke (imported for steel, not melting copper nuggets) in the smelter, and when I forbade the coke, it wouldn't take the charcoal as a substitute.