One thing you might not have done, or your theme anyway.
People use wordpress tags willingly, but they generate <li>s and <ul>s themselves.
Go through your code, and see where your missing it.
And the validation should give you the exact line of the error anyway.