I have the same problem. Clear calls list and it later reappears. Powering the phone down does not help and there seems to be no obvious pattern to when the calls reappear.
I've had this same problem. I'm thinking it might be an iCloud issue. I started my iPhone from scratch as new and one day all of my recent calls were back on too.