@michelle.foy I assume that you are running from a custom build of Kibana, since you mentioned that you are already modifying the logo in the corner. If that is an incorrect assumption, let me know.
If that is the case, you need to modify the kibana.js file found in /src/plugins/kibana/public/kibana.js
Find this line: .setNavBackground('#222222222') and modify that hex value to whatever you want.
Let me know if that solves your problem!