On my 8830, is there a way to do a mass delete of my call log entries? I can delete one record at a time, but now I have several and one-at-a-time is way too much work.

While in your list of Messages, press ALT+P and you'll get all the phone logs. Then press T to go to the top of the list, press the Menu button, and click Delete Prior.

go to messages > menu > view folders > call log > menu > delete all prior

Or, to delete a group of them...press and hold the shift key while scrolling through them and then hit the backspace key once you've established your selection.