Possibly this depends on the type of phone or details of the Verizon account. For my phone I see an option on the web site to enable or disable calling international (i.e., non-US) numbers. I've always had it set, but I assume the default may be off for some customers.