I'm just one error away from validating my site's xhtml, and I have no idea how to fix it.

The message:
Error Line 84 column 12: end tag for "ul" which is not finished.

The code in question:
<tr id="navfooter"><td bgcolor="#FFFFFF">
<ul class="navfooter"><li><a href="http://www.confutatis.org">© Elaine</a></li>
<li><a href="http://validator.w3.org/check?uri=http%3A%2F%2Fdesign.confutatis.org%2F">XHTML 1.0</a></li>
<li><a href="http://jigsaw.w3.org/css-validator/validator?uri=http%3A%2F%2Fdesign.confutatis.org">CSS</a></li>
<li><a href="http://wordpress.org/">Wordpress</a></li>
<li><a href="#">TOP</a></li></ul></td></tr>
</table>
</body>
</html>

My site: http://design.confutatis.org
I've double and triple checked the </ul> tag to see if it's incorrectly nested, but it looks fine. The strange thing is that the top navigation bar on my site - which also uses the same code - validates fine.

Another odd thing is that my site validates when I refresh the validation page at random. Is this a true validation error, or just something on the w3c page that screws things up?

Well, I saw no syntactical errors myself, and I (re)validated your index page upwards of five times and it validated as valid XHTML 1.0 Transitional during each. So, either congratulations on fixing the error or you may want to reduce your dosage. ;)