reinstalling the gallery module wont help, the data will still be there. what needs to happen is to figure out how it got into that state and stop that from happening.
What that error is saying is that there already is an image that exists for in the location that you're trying to upload it to and that there can only be 1 order for any one image.
So somehow the image order is in the database before the image has been created. This is why
@ultrajam is asking about altering the database.
any deleting of gallery images lately if yes, how?