I've never heard "you're overqualified" specifically, but I lost count of how many times I heard "we can't pay what someone with your skillset is worth and don't think you'll stick around because of it" when I was unemployed between jobs #3 and my current one for 5 months, desperately applying to any and all positions that got posted, like 'website maintenance assistant', 'adwords manager', 'forms developer' and 'frontend developer'.
Eventually two weeks before my unemployment would have run out, a senior java ecommerce developer position opened up, to which I currently cling with dear life. :)
This might just be regional/bad job market thing, I don't know. Never lived anywhere else but Maine.
Unfortunately, ability to relocate might be essential in some circumstances. At least until employers are more willing to hire remote workers, assuming that happens eventually.