Mine does that sometimes. It seems to happen right after I get my voice mail, if I hang up quickly and then dial the number it fails. It normally straightens itself out if i wait a moment and then place the call again. Recently it just did it on every call i tried to make and a battery pull fixed it. I dont know if it is device specific or what.
It is not so bad that i want to replace the device, its more effort doing that then doing a battery pull once in a while.
I have had other non blackberry devices do that as well so I thought it maybe was something with verizon. I guess if it happens every day I would call customer service to see if there is an issue with the line or take it in.
What I have learned after swapping out my Pearl a number of times is that its always something. Every one of them had some sort of individual quirk. My curve seems to be much more stable for the exception of the random and infrequent call falled.