Fast forward a week and Apple has binary rejected the update on copyright grounds as you are able to find Disney images (amongst other names) using the app. I use Tumblr's API and Imgur's API to retrieve the the GIFs, the same GIFs that are available in the Tumblr app and through the Safari browser.
What the f*ck?
Looks like Matt Cheetham's GIF Finder will make its way back into the App Store after his rejection appeal landed him a call from Cupertino:
The rejection was largely due to the inclusion of 3 categories in the categories tab. "Doctor Who", "Nigel Thornberry" and "Star Trek" are the root of the problem. Apple has particular issue's with the copyright of these 3 categories which mean my app couldn't be approved.
The inclusion of images of Nigel Thornberry in the screenshots for the app were the secondary cause of the rejection.