One downside to early voting that I've seen is for the primary. Candidates have a habit of dropping out of big primary races in the month before the election day; just think about the presidential primary process. That causes a lot of wasted votes, and may well have been decisive in the IL gov race in 2010.
I think the real problem here is the voting system, not the early voting. A ranked voting system (e.g. instant runoff, condorcet) could significantly alleviate the issue you cite. Even when all the candiates stay in the race, votes get wasted in the same manner. It's just with the early dropout, some voters whose votes would have been wasted (without the dropout), may have had a chance to not waste their votes if they waited. But with a good ranked voting system, much less is wasted in general.
