Okay, had an odd thing occur to one of my automatons. He was deconstructing floor, and managed to find himself floating on his own little spot of floor long enough to run out of fuel. His builder buddy then built a floor next to him, but then deconstructed the floor he was stuck on, which caused him to fall down a couple levels.
I was unable to get him refueled, or deconstructed after that point. Tried everything I could to move him around etc. Even waited for a new gnome to show up to see if there was any reason my current crew didn't see the problem.