You're getting into extreme problem areas for sure. My thought is that something is broken either in AT&T's database or Apple's database. You say you got a new SIM and ran through the activation steps as documented here:
http://tech.kateva.org/2015/10/at-iphone-6s-with-ios-902-problem-no.html
So next up might be something here that could help: http://tech.kateva.org/2015/10/to-contact-imessage-server-try.html
Also if you go to iCloud on web you'll see devices associated with your iCloud account: http://tech.kateva.org/2015/10/icloud-settings-remove-devices-restore.html
So if you think AT&T's database is now correct (that's what I think a new SIM does, forces refresh there) you could try:
1. Backup to iTunes AND to iCloud.
2. On iCloud per above remove device from Apple's records.
3. Wipe device
4. Activate as a brand new device with NO Apple ID. Does call forwarding work now?
5. Wipe device
6. Restore from iCloud (not iTunes) backup.
All of this is about trying to get Apple to refresh it's database records. But if step 4 fails then I think it's an AT&T problem...