Searching Plugins gives "an Unexpected Error has occurred" on certain words

if I try to do a search or click some of the links it will fail with the “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. Try again” error. I have searched and seen many people having this issue with trying to search word press plugins from the Control Panel and seen many suggestions as to de-activate plugins and retry, check cURL, check OpenSSL, etc I have tried them all to no avail.

I can manually ftp the plugins to the site and install it that way so its not the end of the world. The weird thing is in the Control Panel when you try to add a new plugins there are a list of plugin tags. It will work for several of them and fail for the rest. If I do a “search” and then type in the exact name of the tag as it appears in one of the links (that I already know works) then the search works. Sometimes if I change just 1 letter to make a new term it will fail. Sometimes if I take a term that doesn’t work and add a letter to the end it will work (without finding anything). For example a search for RSS works, a search for SEO fails with the error, but a search for SEOS returns 0 results. Other things like Nimble Portfolio I can successfully do a search on.

I have installed the “html tester” plugin as detailed in this thread
http://wordpress.org/support/topic/37-search-for-plugins-in-cp-gives-unexpected-error?replies=39
and it passes all of them. The fact that it works for some things but not others is what has me confused.

I have included a pic of which tags work
http://imgur.com/dZgSSus