Firstly, I don't think pgq updates catalogs directly, it simply truncates the queue tables when rotating them (which updates the relfilenode in pg_class, of course).
Secondly, we're occasionally seeing this on systems that do not use pgq, but that do VACUUM FULL on custom "queue" tables. The symptoms are exactly the same ("ERROR: could not map filenode"). It's pretty damn rare and we don't have direct access to the systems, so investigation is difficult :-( Our current hypothesis is that it's somewhat related to subtransactions (because of triggers with exception blocks).
Jeremy, are you able to reproduce the issue locally, using pgq? That would be very valuable.
We have tried but have been unable to reproduce it. If we do encounter it again, we will plan on reporting back and seeing if we can do some deep debugging.