Sony Ericsson K800i not saving missed call entries

Just had my K800i stop recording Answered, Dialled or Missed calls! I made two changes, one of which will have fixed it, try them in this order:

1. View call history ("All" tab), press "More" and select "Delete all". Press "Yes" if prompted. Restart the phone.
2. If step (1) doesn't work, go into Menu->Settings ("General" tab), choose "Master reset", then the "Reset settings" option (this doesn't delete contacts etc).

Do backup before you try any of these tips!