Yes, it has to do with two FKs. The model is used by EF to define DB command ordering. It doesn't verify the details of the data you enter. It looks for an ordering that will be effective in every situation, but there isn't one in your instance because your model allows for the creation of two records—one in each table—that will be dependant on one another. They cannot be inserted in this situation in a single pass. The first one would simply be inserted into the database without the dependency to the second one, followed by the updating of the first one with the dependency to the second one. This isn't how EF operates.
Others may disagree, but over time I've come to the notion that history tables function best when they aren't constrained by various referential rules. This, for instance, enables the preservation of deleted data history from primary tables. Does StatusHistory's FK need to be checked? Even if you don't have an FK, you can still keep the CheckID and do a manual Linq query to retrieve the Check's history, but you will lose the navigation property property.