Fixing "open id_rsa failed: Permission denied." in RHEL6

Super quick answer: sudo yum remove selinux*

Running Red Hat Enterprise Linux Server release 6.x? Cannot generate SSH public/private keys with ssh-keygen? Me too!

user@ server:~$ ssh-keygen -t rsa
Generating public/private rsa key pair.
Enter file in which to save the key (/home/user/.ssh/id_rsa): 
Could not create directory '/home/user/.ssh'.
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
open /home/user/.ssh/id_rsa failed: Permission denied.
Saving the key failed: /home/user/.ssh/id_rsa.

I searched the intertubes, and all thread responses say to check the file permissions or my $HOME environment variable. They were fine. The only odd result in the list was: http://rhn.redhat.com/errata/RHBA-2010-0013.html which includes a paragraph:

* SELinux denials caused by the ssh-keygen's
"system_u:object_r:initrc_exec_t" context caused ssh-keygen to fail to
generate public/private RSA key pairs. These updated SELinux policy rules
allow ssh-keygen to successfully generate public/private RSA key pairs as
expected. (BZ#538453)

The problem should have been repaired in the previous version of Red Hat according to the advisory. There was no reason SELinux should be installed on the system, but considering all the other extraneous software I'd already removed, I figured it was.

user@ server:~$ sudo yum remove selinux*
Loaded plugins: product-id, rhnplugin, security, subscription-manager
Updating certificate-based repositories.
Setting up Remove Process
Resolving Dependencies
--> Running transaction check
---> Package selinux-policy.noarch 0:3.7.19-126.el6_2.4 will be erased
---> Package selinux-policy-targeted.noarch 0:3.7.19-126.el6_2.4 will be erased
--> Finished Dependency Resolution

Yes, it was. Once I removed SELinux, ssh-keygen ran successfully. So frustrating...

user@ server:~$ ssh-keygen -t rsa
Generating public/private rsa key pair.
Enter file in which to save the key (/home/user/.ssh/id_rsa): 
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in /home/user/.ssh/id_rsa.
Your public key has been saved in /home/user/.ssh/id_rsa.pub.

Note: This was causing a fprint failed error in gitolite's gl-setup also.