I am working on a 3d editor type program. I use local cube maps for static reflections. Because this is an editor, users can move otherwise static objects around. This means the local cube maps need to be updated. However, if many local cube maps are affected by moving a large object, it would take a bit of time to update all the cube maps. My idea was to have a "GraphicsWorkQueue" where tasks would be added to (like update cube map). My rendering engine would then proceed to do one of these tasks per frame. This might create a temporary drop in frame rate, but not a complete stall so the program will remain responsive. Does this sound reasonable? Or is there a better way people handle this issue?

It doesn't sound unreasonable to me. We just make the artists press a button to re-bake probes, and that works out well enough. For us baking the probes is a pretty heavy operation and our overall framerate inside the editor isn't that great to begin with, so I don't think background updating approach would work out too well for us.