I can't think of any reason that they wouldn't be saved, however they may not be displayed due to an option you can make. Go to your call history and check under the word Phonebook in the upper left hand corner. It should say All Calls. If it says anything else that could be why you aren't seeing them in your history. You can choose from All Calls, Incoming Calls, Outgoing Calls, Missed Calls, and Recent Calls.
If it's not an option you made by mistake in those options, does their number (the last number dialed or called in) still show in the dialer when you open it as if to make a call? If not then you could have something going on. Post back your findings and I'm sure someone will offer more advice.