Foreach - check and save only those that are not in the DB

Do this:

    // Recebendo o array com os ID´S
    $checkboxes = $_POST['check'];  

    $IdTreinamento = $_POST['IdTreinamento'];    

    // Verificando os Colaboradores existente 

    mysql_select_db($database_conexao, $conexao);
    $query_rsVerifica = "SELECT * FROM treParticipantesTreinamento WHERE IdTreinamento = $IdTreinamento";
    $rsVerifica = mysql_query($query_rsVerifica, $conexao) or die(mysql_error());
    $totalRows_rsVerifica = mysql_num_rows($rsVerifica);
    $trePT = Array();
    if ($totalRows_rsVerifica > 0)
       while ($row_rsVerifica = mysql_fetch_assoc($rsVerifica)) $trePT[] = $row_rsVerifica['IdColaborador'];



// laço para buscar ID´s e efetuar cadastro
foreach($checkboxes as $IdColaborador) {

    // Se colaborador existir passa para próximo
    if (in_array($IdColaborador, $trePT)) continue;

    // Buscando dados do Colaborador
    mysql_select_db($database_conexao, $conexao);
    $query_rsRegistro = "SELECT * FROM comColaborador WHERE IdColaborador = $IdColaborador AND ativo = 1";
    $rsRegistro = mysql_query($query_rsRegistro, $conexao) or die(mysql_error());
    $row_rsRegistro = mysql_fetch_assoc($rsRegistro);
    $totalRows_rsRegistro = mysql_num_rows($row_rsRegistro);

    // Buscando dados do Treinamento                
    mysql_select_db($database_conexao, $conexao);
    $query_rsTreinamento = "SELECT * FROM treTreinamento WHERE IdTreinamento = $IdTreinamento";
    $rsTreinamento = mysql_query($query_rsTreinamento, $conexao) or die(mysql_error());
    $row_rsTreinamento = mysql_fetch_assoc($rsTreinamento); 
    $totalRows_rsTreinamento = mysql_num_rows($row_rsTreinamento);

    // Dados do Colaborador
    $Nome = $row_rsRegistro['nome'];
    // Dados do Treinamento
    $Horas = $row_rsTreinamento['CargaHoraria'];
    $FezTreinamento = 0;    
    $Log = $row_rsTreinamento['Log'];       

    // Inserindo dados no banco de dados se não existir cadastro        
    mysql_select_db($database_conexao, $conexao);
    $sqlTreinamento = "INSERT INTO treParticipantesTreinamento ( 
                    IdTreinamento, 
                    IdColaborador,
                    Nome,
                    Horas,
                    FezTreinamento,
                    Log ) 
                VALUES (
                    '$IdTreinamento', 
                    '$IdColaborador',
                    '$Nome',                        
                    '$Horas',   
                    '$FezTreinamento',                      
                    '$Log')";                               
    $resultado = mysql_query($sqlTreinamento, $conexao) or die ("Erro Inserindo Registro: " . mysql_error());

    // 1 = TRUE, 2 = FALSE
    $status = $resultado;       

} // fim do foreach*/

Avoid using the mysql_ * functions because they are in the process of being discontinued. Instead use PDO or mysqli.

An example of optimizing your code would be using prepared statements:

$conn = new PDO('connstr', 'usuario','senha');
$prepared = $conn->prepare("SELECT * FROM comColaborador WHERE IdColaborador = :ID AND ativo = 1");

foreach($checkboxes as $IdColaborador) {
  $prepared->bindValue(':ID', $idColaborador, PDO::PARAM_INT);
  $exec = $prepared->execute();
}

With the above technique you 'prepare' the employee query only once in the bank and change only your parameter to each employee. This will make the code much faster.