Jenkins 1.505
Jenkins GIT plugin 1.3.0
Jenkins GIT client plugin 1.0.4

Git projects are all accepting the git URL and the clone is succeeding, easily verified by checking the contents of the workspaces.

I can go to the workspace at the command line and do things such as:
sudo -u userJenkinsRunsAs git pull
sudo -u userJenkinsRunsAs git add someFile
sudo -u userJenkinsRunsAs git commit -m "testing"
sudo -u userJenkinsRunsAs git push

and all of those work, which to me rules out an ssh key issue. The clone in Jenkins even works, but somehow it is not using the keys when doing the part it calls "Fetching changes".

Once the plugin attempts to fetch changes during a build, this is happening consistently:

Building in workspace /mnt/jenkins/jobs/nativeDependencyBase/workspace
Checkout:workspace / /mnt/jenkins/jobs/nativeDependencyBase/workspace - hudson.remoting.LocalChannel@39e6697e
Using strategy: Default
selected Git installation does not exists. Using Default
Last Built Revision: Revision 2a2765e4045956a91be3d9bff4f19feaffa8ffc0 (origin/master)
Fetching changes from 1 remote Git repository
ERROR: Problem fetching from origin / origin - could be unavailable. Continuing anyway
hudson.plugins.git.GitException: org.eclipse.jgit.api.errors.TransportException: git@github.com:myuser/myproject.git: UnknownHostKey: github.com. RSA key fingerprint is 16:27:ac:a5:76:28:2d:36:63:1b:56:4d:eb:df:a6:48
at org.jenkinsci.plugins.gitclient.JGitAPIImpl.fetch(JGitAPIImpl.java:212)
at hudson.plugins.git.GitAPI.fetch(GitAPI.java:230)
at hudson.plugins.git.GitSCM.fetchFrom(GitSCM.java:793)
at hudson.plugins.git.GitSCM.access$000(GitSCM.java:57)
at hudson.plugins.git.GitSCM$2.invoke(GitSCM.java:976)
at hudson.plugins.git.GitSCM$2.invoke(GitSCM.java:942)
at hudson.FilePath.act(FilePath.java:865)
at hudson.FilePath.act(FilePath.java:838)
at hudson.plugins.git.GitSCM.determineRevisionToBuild(GitSCM.java:942)
at hudson.plugins.git.GitSCM.checkout(GitSCM.java:1101)
at hudson.model.AbstractProject.checkout(AbstractProject.java:1353)
at hudson.model.AbstractBuild$AbstractBuildExecution.defaultCheckout(AbstractBuild.java:683)
at jenkins.scm.SCMCheckoutStrategy.checkout(SCMCheckoutStrategy.java:88)
at hudson.model.AbstractBuild$AbstractBuildExecution.run(AbstractBuild.java:588)
at hudson.model.Run.execute(Run.java:1567)
at hudson.maven.MavenModuleSetBuild.run(MavenModuleSetBuild.java:477)
at hudson.model.ResourceController.execute(ResourceController.java:88)
at hudson.model.Executor.run(Executor.java:237)
Caused by: org.eclipse.jgit.api.errors.TransportException: git@github.com:myuser/myproject.git: UnknownHostKey: github.com. RSA key fingerprint is 16:27:ac:a5:76:28:2d:36:63:1b:56:4d:eb:df:a6:48
at org.eclipse.jgit.api.FetchCommand.call(FetchCommand.java:137)
at org.jenkinsci.plugins.gitclient.JGitAPIImpl.fetch(JGitAPIImpl.java:208)
... 17 more
Caused by: org.eclipse.jgit.errors.TransportException: git@github.com:myuser/myproject.git: UnknownHostKey: github.com. RSA key fingerprint is 16:27:ac:a5:76:28:2d:36:63:1b:56:4d:eb:df:a6:48
at org.eclipse.jgit.transport.JschConfigSessionFactory.getSession(JschConfigSessionFactory.java:142)
at org.eclipse.jgit.transport.SshTransport.getSession(SshTransport.java:121)
at org.eclipse.jgit.transport.TransportGitSsh$SshFetchConnection.<init>(TransportGitSsh.java:248)
at org.eclipse.jgit.transport.TransportGitSsh.openFetch(TransportGitSsh.java:147)
at org.eclipse.jgit.transport.FetchProcess.executeImp(FetchProcess.java:136)
at org.eclipse.jgit.transport.FetchProcess.execute(FetchProcess.java:122)
at org.eclipse.jgit.transport.Transport.fetch(Transport.java:1104)
at org.eclipse.jgit.api.FetchCommand.call(FetchCommand.java:128)
... 18 more
Caused by: com.jcraft.jsch.JSchException: UnknownHostKey: github.com. RSA key fingerprint is 16:27:ac:a5:76:28:2d:36:63:1b:56:4d:eb:df:a6:48
at com.jcraft.jsch.Session.checkHost(Session.java:718)
at com.jcraft.jsch.Session.connect(Session.java:313)
at org.eclipse.jgit.transport.JschConfigSessionFactory.getSession(JschConfigSessionFactory.java:116)
... 25 more
ERROR: Could not fetch from any repository
FATAL: Could not fetch from any repository
hudson.plugins.git.GitException: Could not fetch from any repository
at hudson.plugins.git.GitSCM$2.invoke(GitSCM.java:981)
at hudson.plugins.git.GitSCM$2.invoke(GitSCM.java:942)
at hudson.FilePath.act(FilePath.java:865)
at hudson.FilePath.act(FilePath.java:838)
at hudson.plugins.git.GitSCM.determineRevisionToBuild(GitSCM.java:942)
at hudson.plugins.git.GitSCM.checkout(GitSCM.java:1101)
at hudson.model.AbstractProject.checkout(AbstractProject.java:1353)
at hudson.model.AbstractBuild$AbstractBuildExecution.defaultCheckout(AbstractBuild.java:683)
at jenkins.scm.SCMCheckoutStrategy.checkout(SCMCheckoutStrategy.java:88)
at hudson.model.AbstractBuild$AbstractBuildExecution.run(AbstractBuild.java:588)
at hudson.model.Run.execute(Run.java:1567)
at hudson.maven.MavenModuleSetBuild.run(MavenModuleSetBuild.java:477)
at hudson.model.ResourceController.execute(ResourceController.java:88)
at hudson.model.Executor.run(Executor.java:237)