I was about to curse Debian for no-longer caring about PPC and then it hit me. Check the date of the machine. Yes, sir, it was 3rd January 1904 – as far as Debian was concerned, the keys were well and truly invalid. More here
So I tried everything I could to fix it. Googled and Googled and Googled to no avail. Lots of people had similar issues, but forcing a re-install of debian-archive-keyring fixed it for them. Others said to use a different mirror.