From your question, it might appear that this problem happens with any theme or plugin that you try to install, but most likely this is not the case -- as only themes or plugins that are coded to establish a secure HTTPS connection with a peer should be able to potentially trigger such an error condition. I find it hardly doubtful that installing from the standard WP.org repository a basic theme (such as "Twenty Ten") or a basic plugin (such as "Hello Dolly")
Thus, you first need to narrow down and isolate the problematic theme and/or plugin by starting from a clean condition and incrementally installing the next item and seeing if this triggers the problem. Alternatively, you might be able to scan the PHP code of the suspected candidates for strings such as "HTTPS", "cert", ... etc.
Once you know which theme(s) and/or plugin(s) are trying to establish the secure connection that is failing, make sure you have the official installation packages and are properly following the installation instructions. Ideally, the install procedure should automate the installation of any necessary, non-standard, Certificate Authority certificates. But, if not, there should at least be explicit instructions on how to install the necessary certificates yourself.
BTW, if you are on a shared host, without full control of the webserver installation, you might not have the necessary permissions to install such certificates yourself.