Quando a função [**SEC_TO_TIME**][1]() é usada o valor retornado é do tipo [**TIME**][2], e as restrições para esse tipo de dado são aplicadas (Mínimo: '-838:59:59' e máximo: '838:59:59').

Como no seu caso há possibilidade de retornar um valor além do limite, uma maneira é converter hora, minuto e segundo separadamente.

Criei a função abaixo, ai fica bem mais fácil de usar nas queries.

    DELIMITER //                                                                              
                                                                                                                                 
    CREATE FUNCTION SEC_TO_TIMEB (in_seconds bigint) RETURNS VARCHAR(15)                                                                                                           
    BEGIN                                                                                     
        DECLARE hours VARCHAR(9);                                                 
        DECLARE minutes CHAR(2);                                               
        DECLARE seconds CHAR(2);                                               
                                                                                              
        SET hours   := FLOOR(in_seconds / 3600);                                              
        SET hours   := IF(hours < 10,CONCAT('0',hours),hours);                                
                                                                                              
        SET minutes := FLOOR(MOD(in_seconds,3600) / 60);                                      
        SET minutes := IF(minutes < 10,CONCAT('0',minutes),minutes);                          
                                                                                              
        SET seconds := MOD(MOD(in_seconds,3600),60);                                          
        SET seconds := IF(seconds < 10,CONCAT('0',seconds),seconds);
                                                                                           
        RETURN CONCAT(hours,':',minutes,':',seconds);                                         
    END //                                                                                    
                                                                                              
    DELIMITER ;

Dessa maneira basta usar a nova função na sua query.

    SELECT      he.empresa,
                SEC_TO_TIMEB(SUM(TIME_TO_SEC(CASE WHEN timediff(hr.hora_final,hr.hora_inicial) < 0 THEN TIMEDIFF(CONCAT('1990-01-02', ' ',hr.hora_final),CONCAT('1990-01-01', ' ',hr.hora_inicial)) ELSE timediff(hr.hora_final,hr.hora_inicial) END))) AS Soma
    FROM        hora_extra AS he
    INNER JOIN  horario_extra AS hr ON hr.codigo = he.cod_extra
    WHERE       he.empresa = 1
    ORDER BY    he.empresa;

Imagino que haja soluções que sejam mais otimizadas, mas creio que não haja outra maneira de realizar o calculo com o TIME sem separar os campos. Se alguém tiver outra maneira de realizar a conversão, ficarei de olho nesse tópico. :)

  [1]: http://dev.mysql.com/doc/refman/5.5/en/date-and-time-functions.html#function_sec-to-time
  [2]: http://dev.mysql.com/doc/refman/5.6/en/time.html