OK bit stumped now with this so figured I'd ask here and see what you ninjas can come up with...
Basically I have a site that was doing really well in Google.com / .co.uk / .ca. After the first (and last) penguin update rolled out I saw a few hits on 3 big keywords.
The site took a bit of a beating in the .com and .co.uk however still ranks REALLY well in .ca.
I've been working on cleaning up some of the sites backlinks especially on the 3 pages of the 3 big keywords that was lost in the penguin update. It's worth noting that it was keyword specific as one of the big synoms still ranks well in .com today.
Over the last few weeks, with the links been cleaned up and a disavow list submitted I'm seeing a few long tail synoms coming back but still nothing on the big terms.
I never received a warning in Webmaster tools for the links, it was the algo penguin hit.
The website is hosted in the US, and I have not set a country target in webmaster tools.
I thought maybe it was the delayed country algorithm update but its now been like this for months so it's not like the .com and .co.uk have not updated I don't think.
I've tried looking into this as much as I can and kind of conceded to the fact I might have to wait for penguin to run again to see if I've cleaned the links up enough to get out of the auto penguin penalty...
I'm assuming that your site is a .com hosted in the US, and that your preference is to rank well in the US, and to do well in all three countries.
From your description, it sounds like many of your US links were discounted, and/or that the backlinks of sites upstream of the sites that are linking to you were discounted. This would weaken sites further down the chain leading to your site.
It may or may not be also that some of your links from Canadian sites, eg, haven't been negatively affected to the same degree, which may be why your Canadian rankings appear to be holding up better.
Additionally, results are term specific. Google.ca is less competitive than Google.com in general, and might be particularly so on the terms you are competing for. I haven't compared the UK and Canada.
Note that in addition to cleaning up bad links, you will most likely, over time, need to acquire new relevant, natural links of good quality to regain prior rankings.
I would spend energy building link-worthy content... and getting the word out to sites which topically relate to you.