I tested the functionality from 9.3 on through 9.4, and it worked in those versions, so if you don't mind I have a few obvious questions:
Is the AppConfig "LargeOverwritesOthers" set to true?
When they are on the Product Image tab, and they click then Large Multi-Image Manager and then choose new images, do they hit the "Update" button on the pop-up? I notice when the images are large it hides the button until you resize the pop-up.
Can you delete the current "old" Micro images, say via FTP? I am wondering if they have a file-lock on them of some sort. If you can, delete and then recreate them.
I noticed that using Large Multi-Image Manager to delete (checking the Delete box, hitting update) leaves the micro image(s). Doesn't really address the problem you're having, but I thought I'd point it out to avoid confusion.