Electronic voting machine implementation, testing and deployment also takes a significant time and effort. Tamper-proofness obviously has a original and natural physical implmentations that do not require first chosing two large prime numbers: tape and sign the damn box! Though you didn't raise the point, some argue that the time it takes to manually count is a problem, as if people seriously can't wait an extra half-day. Just WAIT. It's important.

The clear advantage of paper voting is everyone--the entire electorate-- can see and understand the process. The legitimacy of the outcome depends on this understanding and trust.