That's because you're on OS5. Under OS5, there's now two databases that "want" to behave as one, but don't because RIM programmers are morons and release OSs that then don't get properly tested by Verizon and just get stamped certified in less then a week.
The two databases are Phone History and Phone Call Logs. You'll need to clear it in both places unfortunately.
When you look at the Call Log view in the Phone app, you're looking at the Phone History database info... when you hit the magnifying glass on the bottom toolbar, the phone pulls up the entries for that person from the Phone Call Log database. The two databases (or rather changes to either of them) should be represented in the other, but it doesn't. As a matter of fact, if you hit the magnifying glass button (See History) for a person and then delete even just a single entry on that list, you then cannot hit Menu in the Phone app while having that contact highlighted... the Menu to the left WILL NOT come up.
One workaround to delete the call history is to multiple select as many as you want in the call history and delete them all at once. Not quite the same as deleting the call logs, but it's better than deleting them individually.