I've had similar problems last year. My understanding was that the system gave relevancy or not based on the keyword and the theme of the landing page. For example, you bid on "widget" but your page is about something else, you'd get poor keyword relevancy.
However, talking to a Google rep, they told me that the system will automatically assign poor relevancy if the click rate is poor. In other words, when the QS falls to 3. As CTR is the biggest factor of QS, you need to dramatically increase it. Sure enough, when that eventually happened, the keyword relevancy changed to OK.