Not sure if this is another form of 4579 or a different one. But in 3.3.3 if you dig on a shifting dungeon part, you randomly end up getting the message "you swing at empty air" or "the stone is too hard" even if you started digging on a normal wall. Perhaps it triggers if the dungeon shifts on the same turn as the digging begins/ends?

With enough tedious digging you end up succeeding eventually.