Gaining one level in any skill seems to fall outside the standard "Skills can be listed with or without an associated level. If no rank is listed, then you gain that skill at Level 1 if you do not have it already, or increases its level by one if you are already trained in that field." due to the lack of listing the actual skill, any clarification on this issue would be nice.
You should probably Gain it at Level 1
This case falls between the rules as written so direct rules reference is not really possible. The Connections rule only says:
For each connection you make, you gain one level in any Skill
The argument against the you get it at Level 1 is that going from untrained to level 0 is also upping the level as this means it you no longer get the penalties for untrained use.
But I would argue that you can see the skill you gain from the connection as a skill listed without an associated level and apply the general rule:
Skills can be listed with or without an associated level. If no rank is listed, then you gain that skill at Level 1 if you do not have it already, or increases its level by one if you are already trained in that field
The other argument is that the intend of the connection rule is two fold on one side it rewards you for adding a connection and with that a roleplay hook. On the other hand you gain a level in a skill which means you can chose to start with a higher power character balanced with that you increase your Skill Total making learning new skills more work. Knowing this you can see the intent as raising your Skill Total by one and as untrained skills and Level 0 skills both count as 0 for this total moving a skill from untrained to 0 would not increase the Skill Total
No rank is listed, thus you add 1 rank to an existing skill, or gain a new skill at rank 1. The detail that you choose the skill rather than having a specific skill listed is not significant.
There are very few situations where skills are gained at rank 0 (homeworld background skills, basic training) and, in those cases, you cannot gain or increase the skill above rank 0. In this case, existing skills can be increased to a maximum of rank 3, thus it is not subject to a "rank 0 and no higher" limitation.