How precisely is this reproducible? (Without reference to Debian packages; by starting with an empty $JENKINS_HOME, running different versions of Jenkins using java -jar jenkins.war, managing plugins, etc.)
The matrix-project-plugin was split out of core in 1.561, moved to its own repository. (References from core test code use a binary test-scope dependency.) As of 1.561, it is a bundled plugin, so enabled by default when you run Jenkins. Other plugins compiled against 1.560 or earlier, including old versions of git-plugin (I think git-client-plugin is irrelevant here) automatically get an implicit dependency on it for compatibility; plugins compiled against 1.561 get such a dependency only if explicitly declared, which applies to new versions (currently just betas) of git-plugin. So all this is fine.
My guess is that you started with an old version of core (and an old version of the Git plugin); updated to 1.565.x, causing the bundled plugin to be extracted to $JENKINS_HOME/plugins/matrix-project/; then rolled back core, whereupon matrix-project would still be listed as installed and enabled. (Despite its expressly requiring core 1.561+; currently Jenkins does not enforce plugin-to-core version dependencies at startup. This is filed separately. If JIRA were not so slow to search I would tell you where.) At that point everything should still be fine, since classes in the class loader for git-plugin referring to MatrixBuild and the like should link to the versions of those class loaded from the Jenkins core class loader, ignoring the matrix-project-plugin class loader.
But my suspicion is that something in Stapler doing reflective calls is picking up classes from the matrix-project-plugin class loader and somehow mixing them up with other classes. I cannot offhand see how this would result in a NoClassDefFoundError. Unfortunately the stack trace does not give adequate information about the chain of class loading events (this is a limitation in HotSpot).
At any rate, if my guess about the means of reproduction is correct, then this can just be closed, with the workaround of deleting/disabling the now-unusable Matrix Project Plugin after the downgrade, noting that the future robustness fix is to enforce plugin dependencies better.
Critical
