You have to:
- be in same region
- have armies of similar strength
- if one doesn't have PVP protection, make sure that other isn't having that, too.
Also, after meeting all the req., try to relog/revalidate files one Steam if fails.
Moved to Tech support.
Community Manager - feel free to PM me about any game related issue, bug, question...