I know this is a late reply but (seemingly) the solution has just been released. I had the same problem on Windows Vista Ultimate 64bit. It didn't work yesterday and it works today. The only noteworthy difference? I installed SP1 for Vista.
Hopefully you've found an alternative solution by...
Why would this code not work?
Private Sub TreeView1_BeforeCheck(ByVal sender As Object, ByVal e As System.Windows.Forms.TreeViewCancelEventArgs) Handles TreeView1.BeforeCheck
Dim nd As TreeNode
For Each nd In TreeView1.SelectedNode.Nodes