i don't have a character with that many images in a single gallery, so i can't test this myself, but i wouldn't be surprised if the sheer number of images is what's giving the site issues.
have you considered breaking up the gallery into sub-galleries (under the tabs option)? sub-galleries appear on the main gallery page like normal, but you can sort them individually (by navigating to the sub-galleries' page and hitting "sort images") and that might let you sort your images. if you try to collapse them back into the main gallery by moving the images back, i don't think they'd retain their subgallery sorting though, so this would likely be a permanent solution.