Of the possibilities you listed in the article, my money is on the failure to do the redirects. Luckily, it may not be too late to fix that, if you haven't already.

If you're interested, email me at tobes@longtaildragon.com, and I'll pull a report of every URL that needs a redirect.