Whoa!
Doctor X inadvertently suggested the most obvious solution if you haven't tried already! Don't know why it wasn't the first thing to come to my mind.
Have you tried just opening the trash, copying the files, and pasting them into the Pictures folder or onto the desktop? What happens if you just drag them to the Pictures folder with the option key held?
If permissions were messed up, they wouldn't be on the copy!
Along the same lines, loading and saving GIFs usually* doesn't negatively affect their quality so you could load the images into say, Preview, and then use 'Save As' to save new copies wherever you want.
If those things don't work, there must be a larger problem.