1) Are the .gif files in the same directory as the PowerPoint presentation? If you're working in Windows and you move the PowerPoint file after you've linked the files you may have issues - Windows doesn't do well with relative links.
2) Are the .gif files embedded or just linked? You may want to try embedding them into the file - you'll end up with a bigger PowerPoint file, but it may fix this.
3) How large are the file sizes? Remember, PowerPoint has to try and load each file as you enter the frame.
4) It sounds like you're running this on a laptop - have you tried looking at the presentation on a desktop? Check the system you're working on for RAM, processor speed, etc. to make sure you have enough horsepower to drive this.
5) It used to be that you needed at least 100M continuous space on the hard drive to run video files (so Windows could cache). I'm not sure if there's a similar requirement for .gifs but if it runs fine on another machine and not so well on your laptop you may wish to defragment your hard drive (if you're running on Windows).
Do you really need animated .gifs? Sometimes you do - I've used them effectively to demonstrate mechanical concepts, but the example you gave us, while nice looking, doesn't seem to do anything but demonstrate that you can have motion in a presentation. Remember that PowerPoint audience members are like deer - they'll immediately focus on motion to the exclusion of anything else - not helpful if you're trying to get them to pay attention to things like bullet points that say "Under no circumstances should you ever, ever push the shiny red 'Self-Destruct' switch on the Doomsday device". Seriously consider how important the animated .gifs are before tossing them in. I am even fairly conservative with transitions since I want people focusing on the bullet points, not the animations.