When setting up OCS for Enterprise Voice, it's important to format your Active Directory users' telephone numbers to the E.164 international format, which is +<CountryCode><Area/CityCode><LocalNumber> (see this post by Doug Lawty of Microsoft for more information on why E.164 formatting is important for Enterprise Voice). For instance, North America's country code is 1, area codes are 3 digits and local numbers are 7 digits, so we get something like +14165551111.
Ideally, your personal Outlook contacts should also be formatted to the E.164 standard as well. Outlook 2010 does a better job than previous versions to encourage proper formatting when creating a new contact, but many people will have a lot of legacy contacts that are likely all over the place in terms of formatting. You can use OCS normalization rules to help deal with getting Outlook contacts to format properly in OCS, but I think its a better idea to fix the source data if at all possible.
Telling your users to manually fix up all their contacts could result in mobs of angry users with pitchforks knocking down your door. More likely, they just simply won't bother. To make it easier on users, I've created a VBScript stuffed inside an Exchange Organizational Form that will do the trick nicely.
Create a new blank Organizational Form with instructions on what the form does and a big, fat button on it called NormalizeNumbers (see below for an example).
Click on the View Code button, and paste in this code. Save it and publish the form. If all goes well, users should be able to click the button and all the contacts in their default Contacts folder should be updated to E.164 format. Just in case, they should backup their contacts to another folder. As always, the code provided is to be used at your own risk.