Findlaw[0] has a state by state breakdown of laws regarding the time off. Some require paid leave while others aren't. Rather than a federal voting holiday (which brings its own headaches), lobby your local legislature to add language to make the leave paid. It's more likely to happen in the states that don't have it than it is to happen federally.

[0] http://www.findlaw.com/voting-rights-law.html