Черт, бывает же такое!  
 Только ответил и сам нарвался на ту же колдобину.
То, что я писал выше, отлично работало в 4.0.0, но перестало в 4.0.1
Разобрался, в чем дело. Оказалось, что из-за глюка то ли в QImageReader, то ли еще где-то по пути, воспроизвеление гифки всегда заканчивается с ошибкой после последнего кадра.
Поэтому помог только такой вариант:
void Label::restart ()
{
   if (movie) movie->~QMovie ();
   movie = new QMovie (file_name);
   if (movie->isValid())   
   {
      connect (movie, SIGNAL (finished()), this, SLOT (restart ()) );
      setMovie (movie);
      movie->start ();
   }
   else setText ("!!!");
} ;
Здесь Label - производная от QLabel. Первый if - потому что для первого старта я этот слот запускаю вручную из конструктора.
connect отсюда выносить нельзя, так как нам надо переконнектить наш слот на новый QMovie ().