Check the class of service for the person making the change to the notification device number. Under the COS you'll find a section for restriction tables - there are three RTs - one for outdials, one for transfers and one for fax deliveries. Check the outdial RT and make sure it allows for that number format. By default it wont.
The RT checked is always in the COS of the person making the change, not the COS of the person that owns the notification device - this is a common mistake.