Infection of the brain by the Human Immunodeficiency Virus (HIV) causes irreversible damage to the synaptic connections resulting in cognitive impairment. Patients with HIV infection, showing signs of impairment in multiple cognitive domains, as assessed by neuropsychological testing, are said to exhibit symptoms of HIV Associated Neurocognitive Disorder (HAND). In this study, we use resting-state functional MRI (fMRI) data to distinguish between healthy subjects and subjects with symptoms of HAND. To this end, we first establish a measure of interaction between pairs of regional time-series by quantifying their non-linear functional connectivity using Mutual Connectivity Analysis (MCA). Subsequently, we use a classifier to distinguish patterns of interaction between healthy and diseased individuals. Our results, quantified as the mean Area under the ROC curve (AUC) over 75 iterations, indicate that, using fMRI data, we can discriminate between the two cohorts well (AUC > 0.8). Specifically, we find that MCA (mean AUC = 0.89) based connectivity features perform significantly better (p < 0.05) when compared to cross-correlation (mean AUC = 0.82) at the classification task. A higher AUC using our approach suggests that such a nonlinear approach is better able to capture connectivity changes between brain regions and has potential for the development of novel neuro-imaging biomarkers.