@PainNTheMac, on top of losing contacts, I am having the same issue as you too, no one can hear anything even if the call was connected. Also, I cannot send/receive messages when this happens.
This issue started around the same time with the contact lost issue.
But I found a workaround for the network issue after searching on the net, it works for me.
Basically you just need to go to Settings --> General --> Network --> Flip the Cellular Data between On/Off.
It recovers the mobile network successfully everytime I do this. Still, you wouldn't know when the network is broken again until you try to call or text.
As for contact lost issue, I am using iTunes Windows Contacts Sync backup. Everytime when the contacts are lost, I will just re-sync the contacts using the option "Replace info on this phone", it's the fastest workaround for me without losing any other things like messages/photo/etc. Just don't turn on auto-sync when plug-in your iPhone.
Anyhow, these are all workarounds, not solution, and are totally unacceptable.
I have already given up on waiting for official response on these issues, just waiting to change to another phone soon.