I have a rival, but when I look at the history it says we have never played. How does one become a rival?
The rival is chosen based on the past games with the teams in your conference. I assume it's more precisely based on how close and important the games were. For example, my new rival is the team I lost against in the playoffs and which went on to win the title. My previous rival was the team I played some very tough games against and also beat in the conference final.
The fact that you have never played your new rival suggests that you've just been demoted/promoted or you have just joined the game. (I'm too lazy to check which it is.)