You may keep it in CellStateChanged,CellMouseClick or others but there is delay in it. I dont see exactly where to put this check for the case, may be on MouseMove !

Oh, now you need to have at least one check in every column?

Private Function HasParentAndChild() As Boolean
        Dim hasParentCode As Boolean = False
        Dim hasChildCode As Boolean = False
        For i As Integer = 0 To DataGridView1.Rows.Count - 1
            If CBool(Me.DataGridView1.Rows(i).Cells(0).Value) = True Then
                hasParentCode = True
            End If

            If CBool(Me.DataGridView1.Rows(i).Cells(1).Value) = True Then
                hasChildCode = True
            End If
            If hasParentCode AndAlso hasChildCode Then
                Return true
            End If
        Next
Return false
End Function

Expecting this will do the work

Oh, now you need to have at least one check in every column?

Private Function HasParentAndChild() As Boolean
        Dim hasParentCode As Boolean = False
        Dim hasChildCode As Boolean = False
        For i As Integer = 0 To DataGridView1.Rows.Count - 1
            If CBool(Me.DataGridView1.Rows(i).Cells(0).Value) = True Then
                hasParentCode = True
            End If

            If CBool(Me.DataGridView1.Rows(i).Cells(1).Value) = True Then
                hasChildCode = True
            End If
            If hasParentCode AndAlso hasChildCode Then
                Return true
            End If
        Next
Return false
End Function

Expecting this will do the work

I think you want to check if all DataGridViewCheckBoxCell are checked?
First try to go to count -2, then look at your method, you since you need all check boxes to be checked, you can simply have

 For i As Integer = 0 To DataGridView1.Rows.Count - 2
 If CBool(Me.DataGridView1.Rows(i).Cells(0).Value) = True andAlso CBool(Me.DataGridView1.Rows(i).Cells(1).Value) = True Then
  'just ignore
 Else
  return false
 End If
Next
asParentAndChild = true 

If this doest work please tell us more if all check boxes or not and you can give a screenshoot of your datagrid view..

I am going to go ahead and assume you are checking to see if a certain row has both a parent and a child before returning true.

IF that is the case, then I see one problem (maybe not the one you were looking for) and that is that you are not resetting the hasParentCode/hasChildCode boolean values to false after or before each loop iteration. The problem that will cause is that you may get a hasParentCode in one row and a hasChildCode in a different row which would return true. I'll take a crack at the code for what I mean:

Private Function HasParentAndChild() As Boolean

        Dim result as Boolean = False
        For i As Integer = 0 To DataGridView1.Rows.Count - 1            
            If CBool(Me.DataGridView1.Rows(i).Cells(0).Value) = True andalso
                     CBool(Me.DataGridView1.Rows(i).Cells(1).Value) = True Then
                result = True
                Exit For
            End If
        Next
        hasParentAndChild = result
End Function

I combined your two IF statements into a single IF that checks for both to be true. I also got rid of the two return calls and opted for one (my college professor marked me off points on a test once and said you should never have more than one return statement ) If I understand what you are going for here, this should be a little closer to what you need.

EDIT:
If you don't care where the true values show up, then your original if/elseif statement should work fine.