Updated my site to the latest version 2.1.0p18. Updated every Linux Host to the new agent, placed the apt-plugin in the correct path, checked the permissions.
Rescheduled the CheckMK Service at each host, new agent version is detected and the autodiscovery of the APT-Service works like a charm.
Thank you!