I'm not talking about RHEL4. I'm talking recent Fedoras (within the last year or 2). Making a brand new ~/.ssh/authorized_keys file has never worked for me without running restorecon (which is the thing I can never remember).