bluntforce - 11:31 pm on Sep 21, 2012 (gmt 0)
Some of your traffic has shifted to other site pages, so I wouldn't consider that a problem but more an indicator Google feels your site is fine, but they are looking for a closer match to user intent.
I've been satisfied changing existing phrases like "blue widgets" to phrases like:
"small blue widgets"
"medium round blue widget for sale"
"large blue discounted widgets"
I don't do links and on-page at the same time, on-page is done as a page revision with all changes and any additional copy done all at once. No keyword stuffing or tweaking it later. I use their keyword tool to find higher volume phrases I haven't used and that they feel are related to "blue widgets". Maybe something similar would be helpful in your situation.
You might also try looking at the time on page for that category page. If users are on the category page just long enough to select a different page, then the destination product level pages could be considered more appropriate for the term "blue widgets".
Just some thoughts.