Instead of using some custom two-factor authentication which is bound to a specific phone, they should use TOTP (http://en.wikipedia.org/wiki/Time-based_One-time_Password_Algorithm). Then the same shared secret could be configured into several token generators (e.g. Google Authenticator on Android).
TOTP seems to become the standard for two-factor authentication, given that both Facebook and Google use this (Facebook provides its own limited code generator with their App) and also quite a few other significant services (e.g. Dropbox, Amazon AWS).
Google also provides a pam module for TOTP which allows one to setup TOTP for own services. I tried that yesterday: Installed the PAM module and added a key into Google Authenticator. Result: TOTP secured SSH login (by using normal account password with the token appended). TOTP support can also be added to non-PAM capable applications, for example a TOTP extension for Mediawiki exists. I tried that one as well and it is working great.
Google Authenticator App allows one to configure more than one account, so you can secure different services with TOTP and still have one central token generator App.