P.S. That last post only makes sense if I tell you that I changed the directory from /var/www/blog to /var/www/wordpress
I figured it out. After performing a full reinstall of Ubuntu Server Edition (I have been meaning to anyways), permalinks still didn’t work. For whatever reason, Apache2 wasn’t picking/processing the .htaccess file. I added the following lines to the apache2.conf file in /etc/apache2:
# Include the .htaccess file for WordPress
Include /var/www/wordpress/.htaccess
Once I restarted Apache, it processed the rewite rules and everything works fine!
I have also attempted to remove any Aliases (e.g., phpmyadmin and websvn mentioned above) in order to remove any conflicts. I even removed phpMyAdmin completely, but to no avail.