In Breishis 36:2, Rashi says
Oholibamah: She is [identical to] Judith (mentioned above 26:34). He (Esau) nicknamed her Judith (יְהוּדִית) to imply that she denied the validity of idolatry, so that he might deceive his father.
It seems that the reason the name Yehudis was chosen because it signifies being like a Jew (Yehudi). But this name for Jews only started getting used around the time of the Babylonian exile (it is mentioned in Megillas Esther). It's unlikely that Esav prophetically foresaw this. So then why did he choose to name her after one particular son of Yaakov (Yehuda)?