My build failed as described in this post however unlike aforementioned, Project Collection Build Service was already marked as Contributor. I solved the issue by checking "Allow project-scoped builds". This added another user named [Project name] Build Service.
Shouldn't the Project Collection Build Service permission allow me to create the build? I don't understand why I have to set Allow project-scoped builds for each project. I'm going to forget this and I will need to look it up again when the build fails on my next project.