I'm having the exact same problem. I tried everything mentioned here, but I still can't get it to work? I can view the Prev/Next image in my own Members Gallery, but nothing else. I've checked my paths, and also CHMOD the Gallery/Files directory to 777. I've tried CHMODing 777 on all the directories within Gallery/Files too. I thought maybe it was a usergroup issue, but I'm the admin. I also tried to CHMOD the directories with 755... nothing.
Nevermind, I found the problem. For some reason, the mod - Display Unread Posts and Reputation Comments and vBGallery do not play well together.
I figured this out by placing define('DISABLE_HOOKS', true); at the top of the vBulletin config.php file and disabling all hooks. Once I confirmed that the issue was with one of my mods, I systematically disabled one mod at a time until I found out that Display Unread Posts and Reputation Comments is causing the Prev / Next image links to break.