Unable to add themes or see any under "Featured/Popular/Latest"

I’m on WordPress 3.9, but I’ve been having this issue for a long time (also affected 3.1.).

WHen I go under Dashboard > Appearance > Themes and click on “Add New”, I get to the “Add Themes” section, but when clicking on “Featured”, “Popular”, “Latest” or “Upload Theme”, I get this error message:

An unexpected error occurred. Something may be wrong with WordPress.org or this server’s configuration. If you continue to have problems, please try the support forums.

I cannot share my URL since it’s locally installed in a secure server @work, and you will not be able to access it outside my network. We do use a proxy to connect to the Internet, would it be related to that?

Any ideas on how to troubleshoot this? I saw a couple of suggestions in the forum (defining WP_PROXY parameters), and the website being corrupted and/or hacked, but that’s not my case. This was just installed today, and I cannot get it to work.

Thanks!