Google Apps email DKIM won't authenticate
Solution 1:
After finally talking to Google support I ended up trying a 1024 bit DKIM key instead of a 2048 bit key. That worked.
One thing I noticed is that the DNS record for the 1024 bit key was all one string, whereas I had to break up the 2048 bit key into several strings in the same record. My theory is that Google Admin console doesn't recognize that properly, since the other tools I used (links in the question) validated it OK.