I just had this issue and it turned out I had to put the + in front of the number to get it to work. You can get a + by holding zero on your dialer.

I hope this helps anyone else who has the same issue.