Hi itsjustme,
I'm sorry to hear that you have not been able to update your gallery images in this manner. The eBay tool I referred you to is designed to force eBay to make a new copy from the header/gallery image URL that is on file with any listing and it *should* work for either of the situations that you have mentioned.
I have actually tested the the tool under both sets of circumstances personally using test listings I have posted to my own account and I have never had any problems with it, so I am not sure why your efforts have been unsuccessful.
I have also found that visiting the eBay Revise your Item form for a listing and completing the revision process without making any actual changes forces eBay to make a new copy of the provided image for display in the eBay gallery, so you may want to try that method instead.
Alternatively, if you contact eBay's customer support team about the difficulties you are having using the "Fix your Picture" tool, there may be something that can do to help you out.
-Mike