Not sure why you're having that issue but I've never lost a contact in years and whenever I make a change to one on computer, phone, tablet and even work iPhone, the change is reflected within a couple minutes across all devices. I switch phones at least twice a year now (thank you, Jump On Demand!) and every time my contacts make the switch seamlessly.
Are you using any special characters on your Contact Names or have any Contact manager apps that might be re-writing contact information or pictures (like syncing with Facebook or anything like that?).