Unfortunatly it turns out that untrusted check constrains will not always become trusted after altering the contraint as is done in this article. If you find yourself in this situation, this can come due to the constraint being configured (at create time) as not for replication. This can be seen by querying sys.foreign_keys with the condition is_not_for_replication = 1.

In this situation, which can be by design, only re-creating the foreign key without not for replication will make the desired constraint trusted.

More not for replication can be read here:

http://msdn.microsoft.com/en-us/library/ms152529(SQL.90).aspx