Is the announcement coming from FreePBX or the provider? I seem to remember that the FreePBX message similar to this is not exactly as you quote.
Possibilities include not having an outgoing route for the number you have dialled, or that route’s not modifying the number into the form required by the provider.