Make sure both contacts are online and the video call option will appear.

It's a bit finicky.