Did you originally integrate with the CircleCI OAuth app and then add a pipeline with the new Github App? In my case I could start a pipeline but other users got that error. I asked CircleCI and this is what they said:

This is a known issue we're working on. The solution at the moment is to have each user go into Project Settings > Add Pipeline > Authorize. [...] We're working on making this more clear in the web app in the coming weeks and having a better solution other than going to Project Settings to click the "Authorize" button.