Install Mycelium again and scan in your wallets from the backup printout.

By the way, unless your phone was a Google Play Edition, the new version was pushed by Samsung, not by Google. And Samsung is known as a low-quality company that fills your phone with bloatware, replete with severe defects and security holes that are not repaired by Samsung for very long periods of time. What just happened to you may be a typical example for this. My recommendation to all readers is to think hard before buying Samsung.