Yes, you will need to jailbreak your iPhone. I kind of assumed you'd already done that when you said is their a program to install that can do this. If you're willing to give it a go then grab the Pwnage Tool (see one of the sticky threads at the top of the forum) and follow the tutorial (see the same thread as before). Jailbreaking your iPhone will mean that all the call history will be wiped anyway but you'll be prepared to erase calls etc. again in future.
Alec