Deuterated solvents vs. regular solvents
In general, it is safe to assume that solubilities in non-deuterated and deuterated solvents are much the same, and this would be the logical solvent of choice if looking for a NMR solvent. 

However, there is a small difference in relative solubilities between H/D solvents, and you can gauge potential for differences based on the dielectric properties of the two. By memory, I think H2O/D2O have the largest difference (which is still pretty small).

Another factor that can cause differences in solubilities comes from the relative purity of the two solvents. For instance, many prepackaged deuterated solvents are often drier than bulk bench solvents, and this can sometimes cause significant solubility differences, especially in hygroscopic solvents like DMSO. I've seen countless examples of people claiming a compound was readily soluble in DMSO, only to have it sit like a brick when trying to dissolve in a freshly cracked vial of DMSO-d6.