If you've ever accepted the at&t backup option before, on any phone, you'll have to call up customer care and have them remove it for you. If you've never used it before, you should be able to cancel the operation when it prompts you and it shouldn't pop up again
Edit: I see that you're on Telus so obviously you haven't used it before lol.. You may have to find the service in titanium backup and freeze it to keep it from trying to contact at&t every time you open the address book. I'm sure other ppl using at&t notes have run into this problem before..
If you are on ICS, you can disable it from app management under all... look in the "S's" for Sync then click disable. It may still launch a few times because it is in RAM. So launch it a few times and hit cancel. Reboot and launch contacts again and hit cancel. It should go away after that. If you did sign up for that servce you can disable it online (if you are on ATT).
Since you are on Telus, I am guessing you are running one of the ICS leaks or custom ROMs that use one as a base.