/fill to replace air not working in naturally generated caves/structures

When attempting to execute the command:

/fill ~ ~ ~ ~ ~ ~ block replace air

in a cave/mineshaft or underground structure it did not successfully execute, while I expected it to replace the "air" within the cave. When going to the surface or digging a hole into a wall the command works as expected.