Sorting

I'm not sure why you're having a problem.  I had no problem.  This code works fine for me. (Win2K, VS.NET 2003)

I just started with your code, added several things:
  TrySortCollection.Test -- to setup a list of nodes and call sorts.  (I'm actually testing by eyeballing the output.)
  TrySortCollection -- utils for random numbers
  NodeCollection.Add
  Node.column1
  Node.column2
  Node constructor New
  Node.ToString
  AdvancedSort.Compare -- added an implementation for the existing function.

Try it!   How's it different from what you have?
If my code doesn't work on your machine, we have a real mystery brewing here!

[VB.NET]
Option Explicit On
Option Strict On

Public Class TrySortCollection
    Private Shared r As New System.Random

    Public Shared Sub Test()
        Dim size As Integer = 4
        Dim nc As New NodeCollection
        For i As Integer = 1 To size
            nc.Add(New Node(GetRnd(), GetRnd()))
        Next

        ' Sort by 1st column, and show.
        nc.Sort(1, System.ComponentModel.ListSortDirection.Ascending)
        For Each n As Node In nc
            Debug.WriteLine("1 -- " & n.ToString())
        Next

        ' Sort by 2nd column, and show.
        nc.Sort(2, System.ComponentModel.ListSortDirection.Ascending)
        For Each n As Node In nc
            Debug.WriteLine("2 -- " & n.ToString())
        Next
    End Sub

    Private Shared Function GetRnd() As Integer
        Return r.Next(0, 100)
    End Function
End Class

Public Class NodeCollection
    Inherits CollectionBase

    Public Sub Sort(ByVal columnIndex As Int32, ByVal sortOrder As System.ComponentModel.ListSortDirection)
        Dim sorter As New Node.AdvancedSort
        sorter.ColumnIndex = columnIndex
        sorter.ListSortOrder = sortOrder
        MyBase.InnerList.Sort(sorter)
    End Sub

    Public Sub Add(ByVal node As Node)
        MyBase.InnerList.Add(node)
    End Sub

End Class

Public Class Node
    Public ReadOnly column1 As Integer
    Public ReadOnly column2 As Integer

    Public Sub New(ByVal col1 As Integer, ByVal col2 As Integer)
        column1 = col1
        column2 = col2
    End Sub

    Public Overrides Function ToString() As String
        Return String.Format("Node({0},{1})", column1, column2)
    End Function

    Public Class AdvancedSort
        Implements System.Collections.IComparer

        Private _ColumnIndex As Int32
        Private _ListSortOrder As System.ComponentModel.ListSortDirection

        Public Property ColumnIndex() As Int32
            Get
                Return _ColumnIndex
            End Get
            Set(ByVal Value As Int32)
                _ColumnIndex = Value
            End Set
        End Property

        Public Property ListSortOrder() As System.ComponentModel.ListSortDirection
            Get
                Return _ListSortOrder
            End Get
            Set(ByVal Value As System.ComponentModel.ListSortDirection)
                _ListSortOrder = Value
            End Set
        End Property

        Public Function Compare(ByVal x As Object, ByVal y As Object) As Int32 Implements System.Collections.IComparer.Compare
            'My logic to sort is here
            Dim result As Integer

            Dim xNode As Node = DirectCast(x, Node)
            Dim yNode As Node = DirectCast(y, Node)

            Select Case _ColumnIndex
                Case 1
                    If xNode.column1 > yNode.column1 Then
                        result = 1
                    ElseIf xNode.column1 < yNode.column1 Then
                        result = -1
                    Else
                        result = 0
                    End If

                Case 2
                    If xNode.column2 > yNode.column2 Then
                        result = 1
                    ElseIf xNode.column2 < yNode.column2 Then
                        result = -1
                    Else
                        result = 0
                    End If

                Case Else
                    Throw New ApplicationException("AdvancedSort is improperly configured: ColumnIndex.")
            End Select
            If _ListSortOrder = System.ComponentModel.ListSortDirection.Descending Then
                result = -result
            End If
            Return result
        End Function
    End Class
End Class