Has anyone ever experienced issues with territory security like we have? Here is the issue:

1) We set the comp_secterr on the company summary screen when we create a new company.

2) Our sales staff, who can see other companies in that territory, cannot see the new company

To fix, I have to do an advanced find on the new company and click on the UPDATE TERRITORY button and change the territory again (even though I have verified that the territory field value is set correctly already). 

Any ideas why the security would be messed up like this until I do an UPDATE TERRITORY? I have verified even that the SQL data has the correct territory code set in the COMPANY table.