Vanadium and niobium cation-water complexes, V+(H2O) and Nb+(H2O), are produced by laser vaporization in a pulsed supersonic expansion, mass selected in a time-of-flight spectrometer, and studied with infrared photodissociation spectroscopy using rare gas atom (Ar, Ne) complex predissociation. The vibrational bands measured in the O-H stretching region contain K-type rotational sub-band structure, which provides insight into the structures of these complexes. However, rotational sub-bands do not exhibit the simple patterns seen previously for other metal ion-water complexes. The A rotational constants are smaller than expected and the normal 3:1 intensity ratios for K = odd:even levels for independent ortho:para nuclear spin states are missing for some complexes. We relied on highly correlated internally contracted multi-reference configuration interaction and Coupled Cluster [CCSD(T)] electronic structure calculations of those complexes with and without the rare gas atoms to investigate these anomalies. Rare gas atoms were found to bind via asymmetric motifs to the hydrated complexes undergoing large amplitude motions that vibrationally average to the quasi-C2v symmetry with a significant probability off the C2 axis, thus explaining the reduced A values. Both vanadium and niobium cations exhibit unusually strong nuclear spin coupling to the hydrogen atoms of water, the values of which vary with their electronic state. This catalyzes ortho-para interconversion in some complexes and explains the rotational patterns. The rate of ortho-para relaxation in the equilibrated complexes must therefore be greater than the collisional cooling rate in the supersonic expansion (about 106 s-1).