In my case, all of the graphics (pre-existing) I wanted to use for a project were in animated gif format, so I had no choice but to use it. I couldn't get PIL's gif animation to work either, so instead I wrote a converter to convert gif animations into framestrips, using gifsicle (http://www.lcdf.org/gifsicle/). This could be rigged up to convert and load frames in semi-realtime, but conversion is probably the best bet.
I was getting strange grey colorshifts, like negatives, after seeking with PIL, so it sounds like the problem your having as well.
