Very close! At the moment, your code is looking to see if the currently highlighted (not checked) item's text = "True".
Instead, we need to examine the ItemCheckedEventArgs parameter that's passed into the method:
Private Sub MyCbList_ItemCheck(ByVal sender As System.Object, ByVal e As System.Windows.Forms.ItemCheckEventArgs) Handles MyCbList.ItemCheck
If e.NewValue = CheckState.Checked Then
MyCbList.Items.Item(e.Index) = "Done: " + MyCbList.Items.Item(MyCbList.SelectedIndex)
Else
MyCbList.Items.Item(e.Index) = MyCbList.Items.Item(MyCbList.SelectedIndex).Replace("Done: ", "")
End If
End Sub