Although it won't record phone calls, I am really liking a free app I came across a while back. Allow me to copy and paste something that I wrote about it some time ago:
Sound Recorder: Need to make a voice note to yourself? Want to record exactly what the person your meeting with says for later reference? This program gets it done. Store these digital files directly to your external card to protect that precious memory on the 650. If anything this baby records a little too good. At least with my volume care settings, as I thought my first recording was going to blow my headset speaker! But it comes with both a record volume and a playback volume as well as recording quality level. Even though this program rocks and does a great job of recording there is one feature I miss . . . . . an alarm to prod me to take action on that recording. In other words, you make a quick note to yourself to “call insurance company to check on additional coverage” and then set an alarm to “play your message” at a certain time, and then repeat every so often until you tell it to “shut Up” . .

But still yet, for free, it rocks!