It's a common bug with starting rivals being wonky. After the next month ticks, they will no longer rival you if you can't rival them.
I believe that's a unique condition and is WAD, although I could be wrong, and I don't really understand the reasoning behind it either.Someone hasnt played Byz...
Ottomans are your rival for several years unless they grow while you dont.
Also, no, you cant rival them at start either.