I've used the phone app on my WP8 phone and on my Android...both work very well.
The problem with that app is that in order to get the app set up, you have to have a verification code - which is the original problem! I am going to try re-provisioning the account, but have not had the time yet.