I've had this on my Nexus 5 on a stock rom before and modifying the contacts with Contact Cleaner rectified it. However the problem re-surfaced when I went to a custom rom (cyanogenmod). It was the same contacts, so I dove a bit more into it.
I put the phone in a developer state of bluetooth packet captures (tracing) and found the following failed(numbers redacted):
AT Stream: ATD+1-314-000-0000;\r
When dialing from the console, picking the number from the radio and dialing worked, so I tested a fail/work/fail and the following was present:
Failed:
AT Stream: ATD+1-314-000-0000;\r
Worked:
AT Stream: ATD+14150000000;\r
With a few more lines that are present with it actually dials
Failed:
AT Stream: ATD+1-314-111-1111;\r
To me, it looked like when the voice dialing occurred it was putting the dashes in there, but when dialing from the dash, it didn't. I found an app called Bluetooth Phonebook which handles the syncing of the contacts to hopefully get them to be synced correctly, without the dashes:
https://play.google.com/store/apps/details?id=com.android_rsap.irmctest
Trying the trial version worked, so I paid the 2 bucks for the full version and haven't looked back.
The problem could be one of 3 things really:
1. Default app for phone not set properly - Set Default
2. Contacts not formatted correctly - Contacts Cleaner
3. Contacts not syncing the format correctly - Bluetooth Phonebook
Hope this helps.