Angular js - mostrar / ocultar cargando gif cada nueva ruta

Estoy tratando de alternar (ocultar / mostrar) un gif de carga en cada nueva ruta, por lo que mi lógica sería:

routeChangeStart = mostrar gif cargandorouteChangeSuccess = ocultar gif de carga

Este es mi código:

//ANGULAR
app.run(function($rootScope) {

   $rootScope.layout = {};
   $rootScope.layout.loading = false; 

   $rootScope.$on('$routeChangeStart', function() {

      //show loading gif
      $rootScope.layout.loading = true;

   });

   $rootScope.$on('$routeChangeSuccess', function() {

      //hide loading gif
      $rootScope.layout.loading = false;

   });

   $rootScope.$on('$routeChangeError', function() {

       //hide loading gif
       alert('wtff');
       $rootScope.layout.loading = false;
   });
});

// HTML

<img src="img/loading.gif" ng-hide="!layout.loading"/>

es extraño porque esto funciona para 3/4 rutas cambiadas, entonces deja de funcionar mientras se cambian rutas: O

¿Qué podría ser?

AQUÍ HAY UN EJEMPLO EN VIVO gracias a @Rob Sedgwick:http://plnkr.co/edit/ZpkgRhEAoUGlnXjbLb8b

Respuestas a la pregunta(2)

Su respuesta a la pregunta