Se sei sicuro che non ti interessa di quale valore tenere della seconda colonna, dopo che hai ordinato la VecchiaMatrice fai così...

codice:
Dim NuovaMatrice()
Dim ContatoreNoDoppi As Long
Dim I As Long

ContatoreNoDoppi = 0
Redim Preserve NuovaMatrice(0, 1)
NuovaMatrice(0, 0) = VecchiaMatrice(0, 0)
NuovaMatrice(0, 1) = VecchiaMatrice(0, 1)
For I = 1 To ElementiVecchiaMatrice
    If NuovaMatrice(ContatoreNoDoppi, 0) <> VecchiaMatrice(I, 0) Then
        ContatoreNoDoppi = ContatoreNoDoppi + 1
        Redim Preserve NuovaMatrice(ContatoreNoDoppi, 1)
        NuovaMatrice(ContatoreNoDoppi, 0) = VecchiaMatrice(I, 0)
        NuovaMatrice(ContatoreNoDoppi, 1) = VecchiaMatrice(I, 1)
    End If
Next I
Volendo, anzichè scrivere in una nuova matrice, puoi utilizzare solamente la vecchia (togli solo il Redim e mettilo una sola volta alla fine)