Authy automatically synchronizes all accounts. If a user loses his phone when he buys a new one he'll be able to access back all of his account's by registering the app using the same phone number he previously had.
We go to great lengths to ensure security in our systems. Still you don't necessarily have to trust Authy. Since you are still verifying your username and password on your own systems, even if Authy was compromised, your accounts would still be safe. However is more likely that one of your user's passwords is compromised. In that case Authy will still protect the user, since the attacker would need both the password and the token, but only the owner of the cellphone can know the token.
As soon as the person buys a new phone, he can simply reset his phone at: https://www.authy.com/phones/reset After everything keeps working as usual.
Extremely secure. The token is generated using a 1 way function (SHA-2) and a 256 Bits key. SHA-2 is published by the NSA and it's approved by FIPS 186-2 to secure top secret data. Even if the attacker had access to hundreds of Tokens, it would still be mathematically impossible for him to generate a new valid Token.
If you are inclined to know more, Authy is based on RFC4426.