A simple, two-option system that allows for private vote verification:

  Vote: 0 for Gore, 1 for Bush
  Provide, in the polling booth: a random salt of either 0 or 1
  Publish: vote XOR salt

Now, if you want to lie about what vote you cast, you also lie about the random salt. But you can always check for yourself.

Now, the issue becomes obvious - if someone can falsify votes, why can't they falsify salts as well? Less obviously, this is true of any verification system - abstractly, you can always count the vote one way, and "verify" it the other way. So what you have to do is have completely different possession chains for the vote roll and the salt roll. Make it so that at no point does any one person have access to all three of 1) the voter id, 2) the vote cast, and 3) the salt. This means that nobody has the required information, or access, to undetectably falsify a vote.

Extending this to handle more than two options, and making it easy enough to comprehend that the average voter won't get caught out if they try to lie, is left as an exercise for the reader. But it's possible.