There is possibly some corrupt data in your phone's GSM settings. This gets backed up to your Palm profile as well so even if you do a full or partial erase it keeps coming back to haunt your phone. I am not sure exactly what triggers it and if this is caused by a patch but I suspect it does. I had the same problem a few months ago and got rid of the issue by doing the following:
Go to the last page in launcher "System" -> "Backup" Move the slider from "on" to "off". It will give you a warning that the back up in your palm profile will be deleted. Confirm that. This will give you a clean profile to start with.
Now go to "Device Info" -> "Reset Options" -> third option in red color "Erase Apps & Data".
After device reboots enter only your Palm profile username and password. Do not enter data for individual accounts. After Pre has restarted confirm if all is well. Try making/receiving phone calls. If it looks good then go to "Accounts" and set up your individual accounts for contacts, email, calender, etc.
Hopefully this helps.
I had a similar problem but I was not able to pinpoint exactly what caused it. I suspect it was in someway related to the "Advanced Preferences" framework and settings in the Phone screen. It did something which my GSM service provider did not like. After rebooting people would call me and I would not see any ringing or notification on screen. But after they hung up I would immediately get a missed call notification. I was also unable to make calls. I would reach the phone dial up screen but the number would not dial. If I pressed the green phone icon it did nothing. After a few experiments I finally did the above procedure and it sorted itself out. But I am staying away from the consolidated "Advanced......" series of patches for the time being.
Oh and of course if nothing works there's always the webOS Doctor option. But before you resort to that try the above suggestion as its less cumbersome and time consuming.