That was one of the options mentioned (about still be registered elsewhere), and if thats the case then I really have no idea to fix that! I tried to find an email address for AT&T but haven't had any luck yet from here!
Thanks for the help though, will try the wipe later and see whether that makes a difference anyway