Saber si Insert fue exitoso

Primero que nada déjame decirte que no es necesario especificar el nombre del campo al insertar un nuevo registro, es decir, tu sentencia SQL quedaría así:
cnn.Execute "INSERT INTO evaluaciones VALUES( " _
& " '" & LblIdLlamada & "', '" & ComboAgente & "' , '" & LblFechaLlamada & "', " _
& " '" & LblHoraLlamada & "','" & ComboTipo & "', '" & ComboEvaluador & "'," _
& " '" & Combo4 & "','" & Combo5 & "','" & Combo6 & "','" & Combo7 & "','" & Combo8 & "' , " _
& " '" & Combo9 & "','" & Combo10 & "','" & Combo11 & "','" & Combo12 & "','" & Combo13 & "','" & Combo14 & "', " _
& " '" & Combo15 & "','" & Combo16 & "','" & Combo17 & "','" & Combo18 & "','" & Combo19 & "'," _
& " '" & Combo20 & "','" & Combo21 & "','" & Combo22 & "','" & Combo23 & "','" & Combo24 & "'," _
& " '" & TxtObservacion & "','" & TxtFortalezas & "')"
Ahora, si lo que deseas es que salga el mensaje después que se haya almacenado el registro, pues simplemente escribe el mensaje, y si hay algún error es porque aún no terminas el sistema y debes corregirlo. Pero si lo que deseas es que VB te muestre la descripción del error, te paso el siguiente código de un procedimiento que puedes declarar en un módulo [obviamente debe ser público].
Public Sub ExecuteSQL(sSQL As String) 
    On Error Resume Next
    Cnx.Execute sSQL
    If Err.Number <> 0 Then
        MsgBox "Hubo un error al realizar la operacion" & vbNewLine & _
        Err.Description, vbCritical, "Error"
    End If
End Function
Y lo mandas llamar cuando realices una operación como INSERT, UPDATE o DELETE, por ejemplo:
ExecuteSQL ("INSERT INTO Clientes VALUES("& IdCliente &", '"& TxtCliente &"')")
Si la operación anterior genera un error, el procedimiento hará que se envíe un mensaje indicándome la descripción del error [por ejemplo si hubiese omitido un campo de la tabla Clientes sería algo similar a: "El número de valores de consulta y el número de campos de destino son diferentes"].
Con respecto a lo que dices sobre "siempre dice que no se han guardado" tal vez sea que que valor de la variable no lo cambias, es decir "iRow" debe cambiar a 1 una vez que el registro se ha almacenado y si sólo lo adaptaste a tu sistema sin considerar eso, obviamente te enviará SIEMPRE el mismo mensaje, ya que por omisión las variables tipo Integer toman el valor 0 y si no la declaraste... PEOR el caso.
En resumen:
1.- Usa la isntrucción INSERT y enseguida envía el MsgBox
2.- Si deseas que el MsgBox muestre el siguiente Id:
a) Si ya tenías recuperado el Id [quiero suponer que sí: "LblIdLlamada"], si es así sólo increméntalo. [LblIdLlamada = LblIdLlamada + 1]
b) Si no está recuperado, recupéralo [SELECT MAX(IdLlamada) FROM Evaluaciones] e increméntalo. [LblIdLlamada = Rst(0). Value + 1 (Asumiendo que Rst es una variable de tipo Redordset y que en ella recuperas el MAX de Evaluaciones)]
Espero haya sido útil mi consejo, si tienes alguna duda consúltame para resolverla.
Saludos desde México. Juan Pablo E.P.

Gracias Juanpabl0
1° Lo de los campos de la BD, lo hice así porque esos no son todos los campos, falta en la Query el campo Id_evaluaciones, que es un autonumérico y la clave primara,
2° Lo de las banderas o mensajes de alerta sobre si se cumple o no determida condición lo tengo medio claro y no es mi problema de momento, el tema es como sería la query o código para que una vez gatillado el Insert en la MySql, pueda recoger la respuesta de la bd si el Insert fue ejecutado.
  Tengo en MySql un comando  que me indica los  row  afectados, por ya sea  por un select, insert o update, pero  no se  como calzarlo  con mi codigo en VB
int numerodefilasafectadas=commnad.ExecuteNonQuery();
o
$afectados = mysql_affected_rows()
Espero haberme explicado mejor.

No sé cómo esté la "query" que te permite verificar los [Dios mío habla en español! ¿O no puedes hermano chileno?] "row" afectados, pero te puedo recomendar que después de un INSERT simplemente hagas una consulta [SELECT] y verificar si se han añadido los registros [de la misma manera con un UPDATE, sólo cambiando algunas cosas]; o puedes mostrarme tu "query" para así analizarla y darte una nueva opinión.
Saludos desde México. Juan Pablo E.P.