This means that the agent(s) had an issue and could not connect to the collector during process startup, thus, instrumentation could not be performed. To understand more about the issue, check the agent logs.
Indeed, a process restart might be required to fix this.
It all depends on the individual agents' connections to that collector and whether the collector was up when the application/agent was started. You should be able to see which scenario it was in the logs - but things like a high latency connection (maybe the agents not being located close enough to the collector) can result in this as well as any other scenario that may have disrupted the connection at startup. Each connection is unique so it's not uncommon for some to fail and some succeed if there are any issues like this.
Yes, if the agent doesn't get the information it needs at startup it can't instrument the application and the only way to correct this is to restart the application when the collector is available. Once the agent is instrumented the collector can go offline and recover with no issue but at startup this is critical.