I didn't really notice any issues with the SharePoint site itself, but when I tried to run a backup it would error out. Upon closer examination, I noticed that one of our admins had changed the account Office SharePoint Server Search service was using to run. Although the service was started, it wasn't using the account I'd specified when setting up the Office SharePoint Server Search service through Central Administration.
After setting the service to use the orriginal account through Central Administration - Operations - Services on Server and doing a re-boot the event log errors disappeared and my backups worked again. While looking for the cause of the error on Google, I noticed several other people had a similar issue caused by the search service account not having log on locally rights on the server.