I am creating the environment and link via a post deploy script. I have checked all parameters have a variable and all are linked properly.
This may be your problem. There are quite a few references to take care of and the structure of SSISDB is a little complex.
If you take this out of your post-dep script, does the problem go away?