Cuando intentas hacer una redirección Laravel intenta hacer el redirect de la manera convencional, mandando los HEADERS, pero en el caso de que no pueda mandar los HEADERS, realiza la redirección mediante Javascript.
Es con la redirección javascript con la que muestra ese mensaje.
Como estás viendo el mensaje de redirección, podriamos deducir que hay algún problema a la hora de enviar los headers.
Normalemente la causa más común de que no se puedan mandar los headers es porque tu codigo esta imprimiendo algún texto o algo ( Una vez se hace un echo, print_r, se imprime algún error, etc, ya no se pueden enviar más headers ).
Busca a ver si antes de realizar las redirecciones, en algún sitio, el código está fallando o mandando algo de output.
Igual te ayuda usar error_reporting(E_ALL)
para ver si hay algún warning o error que te esté causando el problema.