I'm not sure what the cause of your issue is, but there was one guy here who had a problem with his electronic steering column lock.
He did mention that it was somewhat common with Altimas, 350Zs, and Cubes.
Not too long after, the same problem cropped up with my brother-in-law's Altima. For him, he just ended up removing the fuse for the ESCL once he was able to get it disengaged. I don't believe he's had any issues ever since.
If it's not the lock, I guess it might be the intelligent key system.
Good luck and let us know if you're able to get to the root of this.