We observe a surprisingly sharp increase in the pair hydrophobicity in the water climethylsulfoxide (DMSO) binary mixture at small DMSO concentrations, with the mole fraction of DMSO (x(D)) in the range 0.12-0.16. The increase in pair hydrophobicity is measured by an increase in the depth of the first minimum in the potential of mean force (PMF) between two methane molecules. However, this enhanced hydrophobicity again weakens at higher DMSO concentrations. We find markedly unusual behavior of the pure binary mixture (in the same composition range) in the diffusion coefficient of DMSO and in the local composition fluctuation of water, We find that, in the said composition range, the average coordination number of the methyl groups (of distinct DMSO) varies between 2.4 and 2.6, indicating the onset of the formation of a chain-like extended connectivity in an otherwise stable tetrahedral network comprising of water and DMSO molecules. We propose that the enhanced pair hydrophobicity of the binary mixture at low DMSO concentrations is due to the participation of the two methane molecules in the local structural order and the emerging molecular associations in the water-DMSO mixture.