Well that is just odd. Have you tried just putting "00" before the country code? That's how the network switches know that the call is international anyway (+ translates to 00).

For example, keying 0044 will dial a UK number the same as +44.