Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Your error happens when we are polling to check if the old documents are deleted. This means your items should be indexed and deleted correctly. Coveo for Sitecore queries CES to check if the new changes done by the rebuild are completed, so you know when everything is committed in the index and have feedback about it :) Any error in the diagnostic page? Have you tried to access the URL up there to see if this error pops up there?
Are you using Coveo for Sitecore version 3 or version 4? What is the link that appears on your item and what are you expecting instead of the link that gives you a "404 error"