Как и большинство документации для Android PhoneNumberUtils очень плохо создано. Попробуйте Locale.GERMANY в качестве метода ввода. Если формат локали недоступен, как вы упомянули, вы должны написать свой собственный метод. Возможно, расширение PhoneNumberUtils и переопределение этого метода - хорошая практика. В любом случае, удачи:).
Редактировать: ответ аспартама мне кажется более логичным.