Yup, this is a common observation. To look at it another way, HCl is less likely to ionise in a non-protic environment (since the anion is not solvated by H bonding) - ie the conjugate acid of chloride is more stable in a non-protic solvent (than a protic solvent), therefore chloride (the corresponding base) is a stronger base in a non-protic solvent.
One example I know numbers for is the phenoxide ion (which is actually a reasonable base, comparable to an amine). The pKa of phenol in water is ~10, whereas in DMSO (dimethyl sulfoxide) it is ~19 - ie. phenoxide is 109 times more basic in DMSO than in water, an enormous difference!