First of all, make sure that all the messages on the phone have been erased. Now make sure the Arduino is reset while already plugged into the phone. After a power up, if the light blinks green, then things are fine and you can go ahead and program!
Programming Fido can be done in two text messages.
First, text Fido the default master pin, "#FIDO" - Fido will make you the owner and you will be allowed to program Fido settings.