A lot of people, including myself, have had the same problem bringing an unlocked AT&T Bold to the Rogers network (which is what FIDO uses), just google the problem and you'll find multiple posts. I've heard the only simple solution is changing the sim card to an older Rogers 3040 model sim card. If FIDO doesn't use a Rogers sim card you're just going to have to go to a FIDO stand and try out multiple sim cards until you find one that works. When I went to Rogers they were going to charge me $40 to get a new sim card so I'm assuming it will be the same for FIDO. However, I didn't want to pay $40 so I found another much more technical solution that is free. If you're interested, just pm to get the details on how to do it because there are a lot of steps.