Possible cause 1 of 3:
3G isn't selected as network mode
You can select which network modes your mobile phone can connect to. If your mobile phone is connected to a 2G network, you can't make video calls.
What you need to do
Select 3G as network mode.
Did this solve the problem?