[zebrone]

Alla fine sono riuscito, posto il codice nel caso servisse a qualcun altro:

private void moveUpToolStripMenuItem_Click(object sender, EventArgs e)
{
    if (treeView1.SelectedNode != null)
    {
	//Memorizzo il padre del nodo che sto spostando: 
	//il nodo spostato sarà ancora figlio suo con indice diminuito di 1
	TreeNode parent = treeView1.SelectedNode.Parent;
	//memorizzo la posizione originale del nodo prima dello spostamento
	int originalIndex = treeView1.SelectedNode.Index;
	//memorizzo l'intero ramo da spostare
	TreeNode branch = treeView1.SelectedNode.Clone() as TreeNode;
	//elimino il nodo dalla vecchia posizione
	treeView1.SelectedNode.Remove();
	try
	{
	    if (parent == null) //se non ho parent sono al livello della radice
	    {
		treeView1.Nodes.Insert(--originalIndex, branch);
	    }
	    else //non sono a livello della radice
	    {
		//inserisco un nodo identico nella posizione appena sopra
		parent.Nodes.Insert(--originalIndex, branch);
	    }
	    treeView1.SelectedNode = branch;
	}
	catch (NullReferenceException ex)
	{
	    MessageBox.Show(ex.Message);
	}
    }
}