"Suddenly when starting up, I am seeing a bunch of permission denied errors during startup (like trying to create something in /var/run). I would post my /var/log/messages but I think this permission problem has also prevented that log file from being written."
Maybe the problem is in the /var directory itself. Check the permissions and ownership of /var. If /var is a mountpoint then check the description of /var in /etc/fstab.
It is also possible that this is a problem with some inode in the file system where /var resides. Boot a rescue CD and run fsck against the partition where /var resides.
Be prepared. Create a LifeBoat CD.