HOla spork, prueba lo que te comento carmagedon, tambien te sugiero que muestres los valores de las variables nombre y apellido antes de insertarlas en la base para saber si estan trayendo bien los valores, podrias hacer unos echos"" aqui:
Código PHP:
$link=Conectarse();
$nombre=$_GET['nombre'];
$apellidos=$_GET['apellidos'];
echo"Nombre: $nombre"; //asi sabemos si las variables traen sus valores
echo"Apellido: $apellidos";
//tambien agregue un punto y coma despues del parentesis del value
//por que una vez no me insertaba valores por eso
mysql_query("insert into prueba (Nombre,Apellidos) values ('$nombre','$apellidos');",$link);
if (!mysql_error())
{
echo "<script language='javascript'>location.href='index.php'</script>";
}else{
echo "Error ". mysql_error();
}
Comentanos como te fue.
Saludos