Ciao,
il problema è che richiami le variabili con due metodi diversi!
nel form scrivi:
<form method="post" action="invio.php">

e poi richiami invio.php in questo modo:
<?php ...*
$db = mysql_connect($dbhost, $dbuser, $dbpass); // Connessione al database
$mail = "mia mail";
$oggetto = "E-Mail";
$testo = "nome: ".$_GET['Nome']."
Cognome: ".$_GET['Cognome'];
...* ?>

Non va bene, devi richiamare le variabili con lo stesso metodo che hai utilizzato nel form, cioè il POST.