I’m a little late to the party, but I ran across this thread while experiencing the same errors and found a different resolution.
When creating an SSIS 2012 package, in the Solution Explorer window you will see the Connection Managers folder at the project level. This seems like the most logical place to create a connection, and should be used when creating a connection that can be used by any package in the project. It is included at the project level, and not the package level.
When running my dtsx package using dtexec, I received the same errors shown above. This is because the connection is not included in the package (just the project). My solution was to go into the package designer, and then in the Connection Manager window, right click the project level connection (which is shown using the “(project)” prefix) and choose “Convert to Package Connection”. This will embed the connection in the actual dtsx package. This alleviated my problem.